基于LINGO的考慮距離約束車(chē)輛路徑問(wèn)題模型與求解

度巍 劉媛 楊鍵鈴

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

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

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

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

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

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

2 模型分析

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

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

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

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

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

MODEL：

sets：

node/1..9/： y;！節(jié)點(diǎn)9是配送中心，所有車(chē)輛從節(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是決策變量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)過(guò)對(duì)結(jié)果的分析得到配送車(chē)輛最優(yōu)的路線如表2所示：

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

4 結(jié)語(yǔ)

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

參考文獻(xiàn)：

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

[2] 馬立肖.求VRPTW問(wèn)題的并行協(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）;國(guó)家自然科學(xué)基金（61771265）; 南通大學(xué)自然科學(xué)類科研基金交通專項(xiàng)課題（13040454）

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