控制工程
控製工程
공제공정
CONTROL ENGINEERING OF CHINA
2014年
3期
409-414
,共6页
车队调度问题%奇点边%最小生成树%欧拉环
車隊調度問題%奇點邊%最小生成樹%歐拉環
차대조도문제%기점변%최소생성수%구랍배
fleet scheduling problem%singular boundary%minimum spanning tree%Euler ring
对于一类基于运行距离最短的车队调度问题,构建了问题的数学规划模型.由于模型难以直接求解,构造网络图对车队问题进行表述.通过求解车队调度网路图的最小生成树,去除最小生成树中车辆和车辆之间连接线,从而将问题分解为一个个单车辆调度问题.对于单车辆调度问题的处理,设计了最小权奇点边添加法.该方法通过构造奇点边集合,使单车辆调度网络图成为所有顶点均为偶点的多重图；进而寻找欧拉环,并删除欧拉环中的重复中间点,最终得到问题的求解方案.最后设计了实例,分别采用图解算法和禁忌搜索算法进行求解.对比发现图解算法在求解车辆调度问题方面具有一定的优越性.
對于一類基于運行距離最短的車隊調度問題,構建瞭問題的數學規劃模型.由于模型難以直接求解,構造網絡圖對車隊問題進行錶述.通過求解車隊調度網路圖的最小生成樹,去除最小生成樹中車輛和車輛之間連接線,從而將問題分解為一箇箇單車輛調度問題.對于單車輛調度問題的處理,設計瞭最小權奇點邊添加法.該方法通過構造奇點邊集閤,使單車輛調度網絡圖成為所有頂點均為偶點的多重圖；進而尋找歐拉環,併刪除歐拉環中的重複中間點,最終得到問題的求解方案.最後設計瞭實例,分彆採用圖解算法和禁忌搜索算法進行求解.對比髮現圖解算法在求解車輛調度問題方麵具有一定的優越性.
대우일류기우운행거리최단적차대조도문제,구건료문제적수학규화모형.유우모형난이직접구해,구조망락도대차대문제진행표술.통과구해차대조도망로도적최소생성수,거제최소생성수중차량화차량지간련접선,종이장문제분해위일개개단차량조도문제.대우단차량조도문제적처리,설계료최소권기점변첨가법.해방법통과구조기점변집합,사단차량조도망락도성위소유정점균위우점적다중도；진이심조구랍배,병산제구랍배중적중복중간점,최종득도문제적구해방안.최후설계료실례,분별채용도해산법화금기수색산법진행구해.대비발현도해산법재구해차량조도문제방면구유일정적우월성.
