基于LINGO的考慮距離約束車輛路徑問題模型與求解

度巍 劉媛 楊鍵鈴

摘要：在《交通運籌學(xué)》《交通系統(tǒng)分析》等交通類專業(yè)課程教學(xué)過程中，作為經(jīng)典組合優(yōu)化問題的車輛路徑問題（VRP）通常是重點教學(xué)內(nèi)容。在目前的VRP求解軟件與相關(guān)學(xué)習(xí)資料方面，介紹考慮距離約束條件的模型及求解不多。本文通過分析考慮距離約束條件，給出相應(yīng)的混合整數(shù)規(guī)劃模型，并基于LINGO軟件編程實現(xiàn)求解，最后通過一個實例說明了代碼的可行性。

關(guān)鍵詞：LINGO;車輛路徑問題;路程約束;網(wǎng)絡(luò)優(yōu)化

中圖分類號：G642 ? ? ? ?文獻標識碼：A

文章編號：1009-3044（2021）30-0112-03

Solving Vehicle Routing Problem with Distance Constraint using LINGO

DU Wei， LIU Yuan， YANG Jian-ling

（School of transportation and civil engineering， Nantong 226019， China）

Abstract： Vehicle routing problem （VRP）， as a classical combinatorial optimization problem， is usually the key teaching content in the course of teaching traffic specialties such as Transportation Operations Research and Traffic System Analysis. In terms of current VRP solution software and relevant learning materials， the model considering distance constraint condition and its solution are not enough. The paper introduces the model and solution considering this conditions， The corresponding mixed integer programming model is solved based on LINGO software programming， and the feasibility of the code is demonstrated by an numerical example.

Key words： LINGO; vehicle routing problem; distance constraint; network optimization

1 引言

經(jīng)典車輛路徑問題的一般定義是：某場站有若干運輸車輛，需要滿足一系列配送點的運輸需求，問如何確定每臺車輛的配送任務(wù)以及路線，使得諸如總路程最短等目標得到滿足。由于該問題具有重要的應(yīng)用價值，幾十年來國內(nèi)外學(xué)者作了大量的研究工作，在目前國內(nèi)交通物流專業(yè)課程中，通常也會將其作為重點教學(xué)內(nèi)容。伴隨著更符合現(xiàn)實的各種因素，經(jīng)典車輛路徑問題還考慮其它各種約束條件，使問題的建模與求解變得更加復(fù)雜，其中考慮最多的三類條件分別為：

1）考慮配送能力約束的車輛路徑問題（CVRP）：配送車輛的載貨量具有上限，即在分配的配送線路中包含總的配送量不能超過一個最大值。

2）考慮時間窗約束的車輛路徑問題（TWVRP）：每個配送點配送時間具有要求，即配送車輛到達配送點的時刻需要在規(guī)定的時間段內(nèi)，根據(jù)實際情況還可以將時間窗約束分為硬時間窗約束和軟時間窗約束。

3）考慮配送距離約束的車輛路徑問題（DVRP）：配送車輛的運輸里程具有上限，即配送路線的總長度不能超過一個最大值。

目前相關(guān)的中文研究文獻及其優(yōu)化軟件更多考慮1，2類車輛路徑問題[1-2]，考慮距離條件的文獻在國內(nèi)不多見，本文采用文獻[4]中的DVRP模型，對其模型進行了分析，進一步給出相應(yīng)的LINGO代碼，并通過一個數(shù)值算例檢驗了代碼求解DVRP的可行性。

2 模型分析

DVRP與CVRP的區(qū)別在于：CVRP中每輛車的載貨量是由各個配送點的需求量決定的，而 DVRP的車輛總行駛距離由各個配送點對間距離決定，如何用數(shù)學(xué)語言描述距離約束成為難點，文獻[4]給出了求解DVRP的模型如下：

設(shè)[N]表示配送點的數(shù)量，[V]表示車輛數(shù)量，[Tk]表示第[k]輛車的最大運輸里程，[cij]表示從第[i]個配送點直達第[j]個配送點的距離，當?shù)赱k]輛車的配送路線中存在從第[i]個配送點直達第[j]個配送點，0-1變量[xijk]取值為1，否則取值為0. [yi]是避免生成子環(huán)路構(gòu)造的實數(shù)變量。DVRP相應(yīng)的混合整數(shù)規(guī)劃模型為：

[min ?Z=i=1Nj=1Nk=1Vcijxijk ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（1）s.t. ? ?i=1Nk=1Vxijk=1 ? ? ?j=1，2，…，N-1 ? ? ? ? ? ? ? ? ? ? ? ? ? ?（2） ? j=1Nk=1Vxijk =1 ? ? ?i=1，2，…，N-1 ? ? ? ? ? ? ? ? ? ? ?（3） ?i=1Nxihk=j=1Nxhjk ? ?k=1，2，…，V，h=1，2，…，N ? ? ?（4） ?i=1Nj=1Ncijxijk ≤Tk ? ? k=1，2，…，V ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （5） ?j=1N-1xNjk ≤1 ? ? k=1，2，…，V ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （6） i=1N-1xiNk ≤1 ? ? k=1，2，…，V ? ? ? ? ? ? ? ? ? ? ? ? ? ?（7） ?yi-yj+Nxijk≤N-1 ? 1≤i≠j≤N-1，1≤k≤V ? ? ? ? ?（8） ?xijk∈{0，1} ?i=1，2，…，N-1，j=1，2，…，N-1，k=1，2，…，V]

其中約束（2），（3）確保每個配送點能被一個且僅僅一個車輛服務(wù)到;約束（4）保證了配送路線的連貫性;約束（5）表達了車輛的路程約束;約束（6），（7）保證了每輛車如果被分配運輸任務(wù)，離開或回到場站不超過一次;約束（8）是避免生成子環(huán)路約束。文獻[5]對如何用約束（8）消除子環(huán)路做作了分析。

在交通運籌學(xué)等課程教學(xué)過程中，一般將旅行商問題（TSP）的混合整數(shù)規(guī)劃模型作為整數(shù)規(guī)劃內(nèi)容的學(xué)習(xí)案例[3]，可以看到上面的模型與TSP模型類似，也是通過引入0-1變量和實數(shù)變量，用數(shù)學(xué)語言描述了各種約束和總的行駛距離最小目標，是非常好的TSP模型拓展。在模型求解上，如果要求交通專業(yè)本科生去動手編寫如遺傳算法、模擬退火等啟發(fā)式智能算法代碼，無疑增加了教學(xué)難度，在實踐中效果不理想，所以最自然的方式是通過前期已經(jīng)講授并且較容易上手的LINGO優(yōu)化軟件，來實現(xiàn)模型的代碼化與求解。下一節(jié)將通過算例來檢驗LINGO求解的可行性。

3 數(shù)值算例

假設(shè)某地區(qū)有9個節(jié)點，其中9號節(jié)點是一個配送中心，其它8個節(jié)點為配送地，有4輛車在配送中心向其它8個節(jié)點配送貨物，9個節(jié)點之間的距離矩陣（單位公里）如表1所示：

每輛車的最大行駛里程為56公里，每次配送貨物各個目的地只需要到達一次。問各個配送地應(yīng)該如何分配給4輛車，一方面能保證每輛車的行駛里程不超過最大里程，同時4輛車總的行駛里程最短。

基于第2節(jié)的模型，對應(yīng)的LINGO求解代碼如下：

MODEL：

sets：

node/1..9/： y;！節(jié)點9是配送中心，所有車輛從節(jié)點9出發(fā)，最后回到節(jié)點9;

vehicle/1..4/：q;！q表示最大行駛距離;

cxc（node，node）： dist;！dist是城市間的距離，t是城市間的行駛時間;

cxcxv（node，node，vehicle）：x;！x是決策變量x（i，j，k）;

cxv（node，vehicle）！：y; ！y是決策變量y（k，i）;

endsets

data：

q=56 56 56 56;

dist=0 8 12 15 18 40 20 32 16

8 0 13 8 20 10 15 22 20

12 13 0 15 20 20 15 15 15

15 8 15 0 20 10 18 18 30

18 20 20 20 0 20 15 15 20

40 10 20 10 20 0 14 18 15

20 15 15 18 15 14 0 14 20

32 22 15 18 15 18 14 0 20

16 20 15 30 20 15 20 20 0;

enddata

min=@sum（cxcxv（i，j，k）：x（i，j，k）*dist（i，j））;

@for（node（j）|j#lt#9：@sum（cxv（i，k）：x（i，j，k））=1）;

@for（node（i）|i#lt#9：@sum（cxv（j，k）：x（i，j，k））=1）;

@for（cxv（h，k）：@sum（node（i）：x（i，h，k））=@sum（node（j）：x（h，j，k）））;

@for（vehicle（k）：@sum（cxc（i，j）：dist（i，j）*x（i，j，k））<=q（k））;

@for（vehicle（k）：@sum（node（j）：x（9，j，k））<=1）;

@for（vehicle（k）：@sum（node（i）：x（i，9，k））<=1）;

@for（cxcxv（i，j，k）：@bin（x（i，j，k）））;

@for（cxcxv（i，j，k）|i#EQ#j：x（i，j，k）=0）;

@for（vehicle（k）：@for（cxc（i，j）|i#lt#9#and#j#lt#9#and#i#NE#j：y（i）-y（j）+9*x（i，j，k）<=8））;

END

在LINGO11平臺上運行后結(jié)果如下圖所示：

經(jīng)過對結(jié)果的分析得到配送車輛最優(yōu)的路線如表2所示：

相應(yīng)總的運輸里程為190公里。

4 結(jié)語

近年來快遞、外賣配送等行業(yè)的興起，使得VRP具有更廣泛的應(yīng)用背景，在交通運籌學(xué)等課堂教學(xué)中如何將理論與現(xiàn)實問題結(jié)合，促進學(xué)生的科研能力，更好地應(yīng)用數(shù)學(xué)方法與軟件解決實際問題成為值得研究的教學(xué)課題，本文將教授內(nèi)容與相關(guān)科研文獻學(xué)習(xí)相結(jié)合，指導(dǎo)學(xué)生如何使用LINGO軟件解決更復(fù)雜的問題，是交通運籌學(xué)、交通系統(tǒng)分析等課程教學(xué)內(nèi)容很好的補充。

參考文獻：

[1] 范月林，周素萍.基于改進遺傳算法的帶時間窗VRP問題研究[J].電腦知識與技術(shù)， 2011， 7（10）：2411-2413.

[2] 馬立肖.求VRPTW問題的并行協(xié)同混合差異演化算法[J].電腦知識與技術(shù)，2012，8（20）：4970-4973，4980.

[3] 韓中庚. 運籌學(xué)及其工程應(yīng)用[M].清華大學(xué)出版社，2014.

[4] R.V.Kulkarni，P.R.Bhave.Integer programming formulation of vehicle routing problems[J].European Journal of Operational Research， 1985，20（1）：58-67.

[5] Martin Desrochers，Cilbert Laporte.Improvement and extensions to the Miller-Tucker-Zemlin subtour elimination constraints[J].Operations Research Letters，1991，10（1）：27-36.

【通聯(lián)編輯：王力】

收稿日期：2021-03-06

基金項目：2020年江蘇省級大學(xué)生創(chuàng)新訓(xùn)練項目（編號：202010304176H）;國家自然科學(xué)基金（61771265）; 南通大學(xué)自然科學(xué)類科研基金交通專項課題（13040454）

作者簡介：度巍，博士，副教授，主要研究方向為交通系統(tǒng)工程。