基于LINGO的考虑距离约束车辆路径问题模型与求解

度巍 刘媛 杨键铃

摘要：在《交通运筹学》《交通系统分析》等交通类专业课程教学过程中，作为经典组合优化问题的车辆路径问题（VRP）通常是重点教学内容。在目前的VRP求解软件与相关学习资料方面，介绍考虑距离约束条件的模型及求解不多。本文通过分析考虑距离约束条件，给出相应的混合整数规划模型，并基于LINGO软件编程实现求解，最后通过一个实例说明了代码的可行性。

关键词：LINGO;车辆路径问题;路程约束;网络优化

中圖分类号：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 引言

经典车辆路径问题的一般定义是：某场站有若干运输车辆，需要满足一系列配送点的运输需求，问如何确定每台车辆的配送任务以及路线，使得诸如总路程最短等目标得到满足。由于该问题具有重要的应用价值，几十年来国内外学者作了大量的研究工作，在目前国内交通物流专业课程中，通常也会将其作为重点教学内容。伴随着更符合现实的各种因素，经典车辆路径问题还考虑其它各种约束条件，使问题的建模与求解变得更加复杂，其中考虑最多的三类条件分别为：

1）考虑配送能力约束的车辆路径问题（CVRP）：配送车辆的载货量具有上限，即在分配的配送线路中包含总的配送量不能超过一个最大值。

2）考虑时间窗约束的车辆路径问题（TWVRP）：每个配送点配送时间具有要求，即配送车辆到达配送点的时刻需要在规定的时间段内，根据实际情况还可以将时间窗约束分为硬时间窗约束和软时间窗约束。

3）考虑配送距离约束的车辆路径问题（DVRP）：配送车辆的运输里程具有上限，即配送路线的总长度不能超过一个最大值。

目前相关的中文研究文献及其优化软件更多考虑1，2类车辆路径问题[1-2]，考虑距离条件的文献在国内不多见，本文采用文献[4]中的DVRP模型，对其模型进行了分析，进一步给出相应的LINGO代码，并通过一个数值算例检验了代码求解DVRP的可行性。

2 模型分析

DVRP与CVRP的区别在于：CVRP中每辆车的载货量是由各个配送点的需求量决定的，而 DVRP的车辆总行驶距离由各个配送点对间距离决定，如何用数学语言描述距离约束成为难点，文献[4]给出了求解DVRP的模型如下：

设[N]表示配送点的数量，[V]表示车辆数量，[Tk]表示第[k]辆车的最大运输里程，[cij]表示从第[i]个配送点直达第[j]个配送点的距离，当第[k]辆车的配送路线中存在从第[i]个配送点直达第[j]个配送点，0-1变量[xijk]取值为1，否则取值为0. [yi]是避免生成子环路构造的实数变量。DVRP相应的混合整数规划模型为：

[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）确保每个配送点能被一个且仅仅一个车辆服务到;约束（4）保证了配送路线的连贯性;约束（5）表达了车辆的路程约束;约束（6），（7）保证了每辆车如果被分配运输任务，离开或回到场站不超过一次;约束（8）是避免生成子环路约束。文献[5]对如何用约束（8）消除子环路做作了分析。

在交通运筹学等课程教学过程中，一般将旅行商问题（TSP）的混合整數规划模型作为整数规划内容的学习案例[3]，可以看到上面的模型与TSP模型类似，也是通过引入0-1变量和实数变量，用数学语言描述了各种约束和总的行驶距离最小目标，是非常好的TSP模型拓展。在模型求解上，如果要求交通专业本科生去动手编写如遗传算法、模拟退火等启发式智能算法代码，无疑增加了教学难度，在实践中效果不理想，所以最自然的方式是通过前期已经讲授并且较容易上手的LINGO优化软件，来实现模型的代码化与求解。下一节将通过算例来检验LINGO求解的可行性。

3 数值算例

假设某地区有9个节点，其中9号节点是一个配送中心，其它8个节点为配送地，有4辆车在配送中心向其它8个节点配送货物，9个节点之间的距离矩阵（单位公里）如表1所示：

每辆车的最大行驶里程为56公里，每次配送货物各个目的地只需要到达一次。问各个配送地应该如何分配给4辆车，一方面能保证每辆车的行驶里程不超过最大里程，同时4辆车总的行驶里程最短。

基于第2节的模型，对应的LINGO求解代码如下：

MODEL：

sets：

node/1..9/： y;！节点9是配送中心，所有车辆从节点9出发，最后回到节点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平台上运行后结果如下图所示：

经过对结果的分析得到配送车辆最优的路线如表2所示：

相应总的运输里程为190公里。

4 结语

近年来快递、外卖配送等行业的兴起，使得VRP具有更广泛的应用背景，在交通运筹学等课堂教学中如何将理论与现实问题结合，促进学生的科研能力，更好地应用数学方法与软件解决实际问题成为值得研究的教学课题，本文将教授内容与相关科研文献学习相结合，指导学生如何使用LINGO软件解决更复杂的问题，是交通运筹学、交通系统分析等课程教学内容很好的补充。

参考文献：

[1] 范月林，周素萍.基于改进遗传算法的带时间窗VRP问题研究[J].电脑知识与技术， 2011， 7（10）：2411-2413.

[2] 马立肖.求VRPTW问题的并行协同混合差异演化算法[J].电脑知识与技术，2012，8（20）：4970-4973，4980.

[3] 韩中庚. 运筹学及其工程应用[M].清华大学出版社，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.

【通联编辑：王力】

收稿日期：2021-03-06

基金项目：2020年江苏省级大学生创新训练项目（编号：202010304176H）;国家自然科学基金（61771265）; 南通大学自然科学类科研基金交通专项课题（13040454）

作者简介：度巍，博士，副教授，主要研究方向为交通系统工程。