本文選題：乘務(wù)調(diào)度 + 換班機會　； 參考：《計算機集成制造系統(tǒng)》2017年01期

【摘要】：傳統(tǒng)列生成方法在求解乘務(wù)調(diào)度問題時,由于搜索二叉樹的節(jié)點數(shù)呈指數(shù)級增長使其難以解決大規(guī)模問題。為避免搜索整個樹節(jié)點,提出一種逐次縮小問題規(guī)模的迭代優(yōu)化方法。針對乘務(wù)調(diào)度問題提出帶有換班機會選擇的最小費用網(wǎng)絡(luò)流模型。利用Dantzig-Wolfe分解原理,將該模型轉(zhuǎn)化為帶有換班機會選擇的集覆蓋模型,并采取列生成方法求解其線性松弛解,以得到原問題的下界。在求解整數(shù)解時,利用線性松弛解信息,逐次確定不被使用的換班機會集,將問題轉(zhuǎn)化為一系列規(guī)模逐次縮小的乘務(wù)調(diào)度問題。對城市公交中的多組乘務(wù)調(diào)度實例進行計算,將結(jié)果與問題下界和常用遺傳算法的結(jié)果進行比較,表明大多數(shù)實例都能在合理的時間內(nèi)取得最優(yōu)解或近優(yōu)解。
[Abstract]:In the traditional column generation method, it is difficult to solve the large-scale problem because the number of nodes in the binary tree is increasing exponentially.In order to avoid searching the whole tree node, an iterative optimization method is proposed to reduce the scale of the problem one by one.A minimum cost network flow model with shift opportunity selection is proposed for the crew scheduling problem.By using the Dantzig-Wolfe decomposition principle, the model is transformed into a set covering model with shift opportunity selection, and the linear relaxation solution is solved by column generation method, and the lower bound of the original problem is obtained.In order to solve the integer solution, the information of linear relaxation solution is used to determine the unused commutation opportunity set step by step, and the problem is transformed into a series of reduced scale crew scheduling problems.In this paper, the author computes several groups of bus crew scheduling examples, and compares the results with the lower bound of the problem and the results of common genetic algorithms. The results show that most of the examples can obtain the optimal solution or near optimal solution in a reasonable time.
【作者單位】： 湖北文理學院數(shù)學與計算機學院;
【基金】：國家自然科學基金資助項目(71501064) 湖北省自然科學基金計劃青年基金資助項目(2014CFB640)~~
【分類號】：U492.22

【相似文獻】

相關(guān)期刊論文 前10條

1 劉琳;谷寒雨;席裕庚;;工件到達時間未知的動態(tài)車間滾動重調(diào)度[J];機械工程學報;2008年05期

2 郭艷東;黃敏;王慶;;鎖定初始調(diào)度的緊急工作單機重調(diào)度問題[J];東北大學學報(自然科學版);2013年05期

3 姜洋;孫偉;丁秋雷;張旭;;考慮行為主體的單機調(diào)度干擾管理模型[J];機械工程學報;2013年14期

4 席裕庚,王長軍;控制、規(guī)劃和調(diào)度問題中的博弈論應(yīng)用[J];中國計量學院學報;2005年01期

5 徐群嶺;;基于免疫優(yōu)化的公交駕駛員調(diào)度問題[J];計算機工程;2010年24期

6 喻道遠;史登松;劉盛強;張三強;;帶模糊排序的移動瓶頸法求解不確定調(diào)度問題[J];機械制造;2011年02期

7 劉鵬;周曉曄;衣娜;;帶有減少線性惡化效應(yīng)的雙代理調(diào)度問題[J];系統(tǒng)工程學報;2011年03期

8 劉曉東;陳英武;龍運軍;賀仁杰;李菊芳;;同型機在線調(diào)度問題研究進展[J];計算機集成制造系統(tǒng);2012年03期

9 姚君遺，，楊善林，左春榮;基于實例FMS的AGV調(diào)度數(shù)學模型與算法[J];合肥工業(yè)大學學報(自然科學版);1995年01期

10 董平;機器調(diào)度問題及求解方法[J];物流技術(shù)與應(yīng)用;1997年01期

相關(guān)會議論文 前10條

1 李建更;涂凍生;馬海濤;;單機拖后時間總和問題交付期擾動時最優(yōu)調(diào)度不變范圍的一種求法[A];第十九屆中國控制會議論文集（一）[C];2000年

2 劉海龍;黃小原;;總的未完工費用最小的多機調(diào)度問題[A];1995中國控制與決策學術(shù)年會論文集[C];1995年

3 沈吟東;曾西洋;;公共交通駕駛員調(diào)度的復(fù)雜性及解決方法[A];’2004計算機應(yīng)用技術(shù)交流會議論文集[C];2004年

4 李兵;蔣慰孫;;Job shop問題的建模及調(diào)度[A];1996中國控制與決策學術(shù)年會論文集[C];1996年

5 王海星;申金升;;智能蟻群算法解決公交區(qū)域調(diào)度問題研究[A];2006年首屆ICT大會信息、知識、智能及其轉(zhuǎn)換理論第一次高峰論壇會議論文集[C];2006年

6 王成堯;汪定偉;;模糊加工時間的單機調(diào)度問題[A];1996中國控制與決策學術(shù)年會論文集[C];1996年

7 齊向彤;涂奉生;;雙交付期E／T調(diào)度問題[A];1997年中國控制會議論文集[C];1997年

8 吳斌;方葉祥;崔志勇;;基于人工蜂群算法的越庫調(diào)度問題研究[A];第25屆中國控制與決策會議論文集[C];2013年

9 方濤;吳受章;;FMS的自適應(yīng)調(diào)度:結(jié)構(gòu)與算法研究[A];1992年中國控制與決策學術(shù)年會論文集[C];1992年

10 劉興初;趙千川;鄭大鐘;;具有不同準備時間和交付期的單機E／T調(diào)度問題研究[A];1998年中國控制會議論文集[C];1998年

相關(guān)重要報紙文章 前2條

1 本報記者 賈科華;火電機組叫苦調(diào)度不合理[N];中國能源報;2012年

2 本報記者 高芳;牽住“牛鼻子” 巧解“推進難”[N];湖南經(jīng)濟報;2008年

相關(guān)博士學位論文 前10條

1 郭鵬;具有分段惡化效應(yīng)生產(chǎn)過程的智能優(yōu)化調(diào)度研究[D];西南交通大學;2014年

2 元野;基于圖著色模型的零擔物流調(diào)度優(yōu)化問題研究[D];哈爾濱工業(yè)大學;2015年

3 李雪松;模糊環(huán)境下若干單機批加工調(diào)度問題的模型及其算法研究[D];哈爾濱工業(yè)大學;2015年

4 湯雅連;關(guān)聯(lián)物流運輸調(diào)度問題研究[D];廣東工業(yè)大學;2015年

5 周理;高效可重構(gòu)陣列計算：體系結(jié)構(gòu)，設(shè)計方法與程序映射技術(shù)研究[D];國防科學技術(shù)大學;2014年

6 馮大光;一類批處理機調(diào)度的理論和方法研究[D];東北大學;2011年

7 孟盈;鋼鐵企業(yè)并行批生產(chǎn)決策與調(diào)度問題研究[D];東北大學;2011年

8 楊磊;內(nèi)容網(wǎng)絡(luò)中內(nèi)容調(diào)度技術(shù)研究[D];重慶大學;2015年

9 李亞志;流水制造單元調(diào)度智能優(yōu)化方法[D];東南大學;2015年

10 丁寧;若干調(diào)度問題的算法研究[D];大連理工大學;2016年

相關(guān)碩士學位論文 前10條

1 張亮;云計算環(huán)境下的資源調(diào)度技術(shù)的研究[D];江南大學;2015年

2 馮卓鵬;重載運輸卸車組織優(yōu)化研究[D];西南交通大學;2015年

3 崔雪源;基于遺傳模擬退火算法的航班著陸調(diào)度問題[D];華中師范大學;2015年

4 王翠;基于超圖模型和相繼干擾消除的鏈路調(diào)度問題的研究[D];曲阜師范大學;2015年

5 張勇;帶拒絕和釋放時間的單機批調(diào)度問題[D];山東大學;2015年

6 吳凡;基于粒子群優(yōu)化算法的風電-火電機組組合調(diào)度研究[D];華北電力大學;2015年

7 趙虎;MTO模式下的制造企業(yè)穩(wěn)健型調(diào)度問題研究[D];重慶理工大學;2015年

8 吉佳紅;基于細菌覓食算法的改進及應(yīng)用研究[D];江蘇科技大學;2015年

9 周超;柔性作業(yè)車間批量問題研究[D];寧波大學;2014年

10 趙興野;工序順序柔性作業(yè)車間描述與調(diào)度研究[D];大連理工大學;2015年

本文編號：1732852