度巍 劉媛 楊鍵鈴

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

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

中圖分類號(hào)：G642 ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼：A

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

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

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

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

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

2 模型分析

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

設(shè)[N]表示配送點(diǎn)的數(shù)量，[V]表示車輛數(shù)量，[Tk]表示第[k]輛車的最大運(yùn)輸里程，[cij]表示從第[i]個(gè)配送點(diǎn)直達(dá)第[j]個(gè)配送點(diǎn)的距離，當(dāng)?shù)赱k]輛車的配送路線中存在從第[i]個(gè)配送點(diǎn)直達(dá)第[j]個(gè)配送點(diǎn)，0-1變量[xijk]取值為1，否則取值為0. [yi]是避免生成子環(huán)路構(gòu)造的實(shí)數(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）確保每個(gè)配送點(diǎn)能被一個(gè)且僅僅一個(gè)車輛服務(wù)到;約束（4）保證了配送路線的連貫性;約束（5）表達(dá)了車輛的路程約束;約束（6），（7）保證了每輛車如果被分配運(yùn)輸任務(wù)，離開或回到場(chǎng)站不超過一次;約束（8）是避免生成子環(huán)路約束。文獻(xiàn)[5]對(duì)如何用約束（8）消除子環(huán)路做作了分析。

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

3 數(shù)值算例

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

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

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

MODEL：

sets：

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

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

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

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

cxv（node，vehicle）?。簓; ！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平臺(tái)上運(yùn)行后結(jié)果如下圖所示：

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

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

4 結(jié)語

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

參考文獻(xiàn)：

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

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

[3] 韓中庚. 運(yùn)籌學(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

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

作者簡介：度巍，博士，副教授，主要研究方向?yàn)榻煌ㄏ到y(tǒng)工程。