基于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）：每个配送点配送时间具有要求，即配送车辆到达配送点的时刻需要在规定的时间段内，根据实际情况还可以将时间窗约束分为硬时间窗约束和软时间窗约束。……