一種多車場多車型ＶＳＰ問題的求解算法

摘要：論文考慮了一種具有模糊指派功能、車輛具有車型利用水平約束和容量約束、顧客有Hard時間窗的多車場車輛調(diào)度問題。同時設(shè)計出兩階段的求解算法，第一階段考慮將各個客戶需求點模糊指派給各個車場；第二階段安排優(yōu)化子路線時，增加了多車型、車型利用水平、硬時間窗的約束。最后，給出一個算例。

關(guān)鍵詞：VSP問題；排序鏈；模糊指派；Hard時間窗

中圖分類號：F506文獻(xiàn)標(biāo)識碼：A

文章編號：1002-3100(2007)10-0037-04

Abstract: This paper concerns the multi-depots vehicle scheduling problem with the function of fuzzy assignment and with the constraints of vehicle-type-utilize level， vehicle capacity and the constraint of had-time window of customer. This paper also proposes a two-phase algorithm， in the first phase， we assign the customer nodes to the appropriate depot by a fuzzy method. In the second phase， in the process of arranging and optimizing the son-routes， we add the constraints of multi-type vehicle and vehicle-type-utilize level and hard time window. At last， an example is given.

Key words: Vehicle Scheduling Problem(VSP）; compositor chain; fuzzy assignment; hard-time window

0引言

多車場、多車型VSP（Vehicle Scheduling Problem）問題是指有多個車場，車場里配備若干輛車，服務(wù)于已知一組顧客，確定每個車場的客戶服務(wù)群，繼而優(yōu)化出一條針對每個車場的子線路求解問題。由于多車場、多車型VSP問題在處理方法上比單車場更為復(fù)雜，更加符合實際，因此，目前國內(nèi)外不少學(xué)者正從事研究這個問題并取得了一些成果。文獻(xiàn)[1]針對對稱和非對稱的多車場VSP問題提出了分枝定界的精確算法；文獻(xiàn)[2]先運用一定的規(guī)則將多車場VSP轉(zhuǎn)化為單車場VSP，再運用單車場方法來解決單個TSP問題；文獻(xiàn)[3]則對多車場問題建立了一個網(wǎng)絡(luò)流模型；文獻(xiàn)[4]提出的Sweep算法根據(jù)就近分配原則，通過計算每個任務(wù)點離車場最近距離與次近距離的比值，按比值從大到小順序?qū)⑷蝿?wù)分派給車場；文獻(xiàn)[5]提出了一個廣義指派模型用于解決多車場分派問題。但已有的成果中要么缺乏考慮實際情況下車場分配中決策者的主觀因素，要么缺乏多車型和時間窗的綜合考慮。

本文在總結(jié)已有相關(guān)文獻(xiàn)的基礎(chǔ)上，將在新構(gòu)建的模型中，除了一般模型中考慮的因素如客戶點與車場距離、配送時間等因素外，還將決策者的主觀因素考慮進(jìn)來，如道路安全狀況、加油的便利程度、道路的暢通程度、過路費過橋費等因素。由于新增了多個因素，因此，第一階段只能按照決策者對各個車場完成各客戶點的綜合滿意程度大小進(jìn)行主觀上的模糊排序并指派，確定出每個車場客戶服務(wù)群。第二階段由于實際問題中多車型情況居多，所以本文設(shè)計了相應(yīng)的算法。

1問題描述與模型構(gòu)建

2算法設(shè)計

2.1算法原理

解決問題過程中，如前所述，將問題求解分為兩個階段，第一階段先對各客戶點上的任務(wù)進(jìn)行指派，第二階段再對各個車場及其客戶群進(jìn)行優(yōu)化。

第一階段中，首先由決策者確定影響最優(yōu)指派的因素集，然后對確定的各個因素下，對確定的每個車場，完成所有任務(wù)按滿意程度大小進(jìn)行主觀上的模糊排序，形成一條排序鏈后，再對排序鏈中位置號與評判向量中各因素的評判數(shù)進(jìn)行合成，得到各車場分配給各客戶點的綜合滿意度大小。

4結(jié)束語

本文考慮了多車場多車型帶硬時間窗的車輛調(diào)度問題，并將模糊環(huán)境下的排序鏈思想引入到各客戶點對各車場的分配上來，設(shè)計了相應(yīng)的算法，拓寬了多車場問題的應(yīng)用范圍，使該類問題求解更符合客觀實際。此外，本文的算法還可以進(jìn)一步改進(jìn)。比如，各客戶點對任務(wù)完成時間要求并不那么嚴(yán)格，可以將模糊思想引入到時間窗中來，相應(yīng)地又可設(shè)計一套模糊規(guī)則來衡量等待時產(chǎn)生的機(jī)會成本或延遲時的損失成本。以后的研究應(yīng)著眼于此，設(shè)計出針對相應(yīng)約束下的可操作性更強(qiáng)的求解算法。

參考文獻(xiàn)：

[1]G.laporte， Y. Nohert and D. Arpin. Optimal Solutions to capacitated vehicle routing problems[J]. Congressus Numerantium，1984，44:283-292.

[2] 郭耀煌，李軍. 滿載問題的車輛路線安排[J]. 系統(tǒng)工程學(xué)報，1995，10(2):106-118.

[3] 張明善，唐小我. 多車場滿載貨運車輛優(yōu)化調(diào)度的網(wǎng)絡(luò)流算法[J]. 系統(tǒng)工程學(xué)報，2002，17(3):216-220.

[4] 丁源，李引珍. 物流配送（集貨）中運輸車輛優(yōu)化的Greedy Sweep算法[J]. 蘭州交通大學(xué)學(xué)報，2004，23(6):140-142.

[5] 杭省策，李懷祖. 多車場車流分配的廣義指派模型及其分解算法[J]. 西安交通大學(xué)學(xué)報，1997，31(12):111-115.

注：“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文?！?/p>