旅行商问题，车辆路径问题的数学规划模型

发布时间：2024-12-19 12:03

使用数学模型简化复杂问题：将大问题拆解成小部分，用数学公式解决。 #生活技巧# #学习技巧# #解题技巧训练#

根据书籍 Snyder, Lawrence V., and Zuo-Jun Max Shen. Fundamentals of supply chain theory. John Wiley & Sons, 2019 中的相关章节整理。

1. 旅行商问题

旅行商问题（Travelling Salesman Problem): 找到一条将所有地点走完，除了起点外，每个地点只经过一次，再回到起点的最短路线。

下图是一个美国几十个城市的 TSP 路线。
在这里插入图片描述

参数

N = { 1 , 2 , … , n } N=\{1,2,\dots,n\}\quad N={1,2,…,n} 地点的集合 c i j c_{ij}\quad cij 从地点 i i i 到地点 j j j 的距离 x i j x_{ij}\quad xij 0-1决策变量，表示路线是否经过从地点 i i i 到地点 j j j

由于从 i 到 j 到距离与从 j 到 i 的距离一般是一样的（ c i j = c j i c_{ij}=c_{ji} cij=cji,对称的），因此 x i j = x j i x_{ij}=x_{ji} xij=xji.

数学模型

构建数学规划模型如下：

min ⁡ ∑ i ∈ N ∑ j ∈ N c i j x i j s.t. ∑ i ∈ N x i h + ∑ j ∈ N x h j = 2 ∀ h ∈ N ∑ i , j ∈ S x i j ≤ ∣ S ∣ − 1 ∀ S ⊂ N , 2 ≤ ∣ S ∣ ≤ N − 1 x i j ∈ { 0 , 1 } ∀ i , ∀ j min∑i∈N∑j∈Ncijxijs.t.∑i∈Nxih+∑j∈Nxhj=2∀h∈N∑i,j∈Sxij≤|S|−1∀S⊂N,2≤|S|≤N−1xij∈{0,1}∀i,∀j

mins.t.i∈N∑j∈N∑cijxiji∈N∑xih+j∈N∑xhj=2∀h∈Ni,j∈S∑xij≤∣S∣−1∀S⊂N,2≤∣S∣≤N−1xij∈{0,1}∀i,∀j(1)

第一个约束条件表示任何一个地点都通过（到达这个地点，从这个地点出发），第二个约束条件为消除子环条件（sub-tour elimination constraint) ，其中 S S S 为 N N N 的子集， ∣ S ∣ |S| ∣S∣ 表示 S S S 中的元素个数。

子环表示所有地点中的某几个地点的路线形成了一个闭环。例如，下图中，本来有 7 个地点，但是却存在两个子环：

在这里插入图片描述

2. 车辆路径问题

车辆路径问题（VRP）与 TSP 问题的区别是，路线中不仅有一辆车，有好几辆车。所有车辆的路线将所有地点走完，例如下图：

在这里插入图片描述

参数

因为 VRP 中不仅一辆车，涉及到分配车辆的问题，所以决策变量也多了些：

N = { 0 , 1 , 2 , … , n } N=\{0,1,2,\dots,n\}\quad N={0,1,2,…,n} 地点的集合, 0 表示起点 N − = { 1 , 2 , … , n } N^-=\{1,2,\dots,n\}\quad N−={1,2,…,n} 地点的集合, 0 表示起点 K K\quad K 一共 K K K 辆车 C C\quad C 每个车辆的容量为 C C C d i d_i\quad di 地点 i i i 的需求量
c i j c_{ij}\quad cij 从地点 i i i 到地点 j j j 的距离 x i j k x_{ijk}\quad xijk 0-1决策变量，表示分配车辆 k k k 从地点 i i i 到地点 j j j y i k y_{ik}\quad yik 0-1决策变量，表示车辆 k k k 是否通过地点 i i i

数学模型

构建数学规划模型如下：

min ⁡ ∑ k = 1 K ∑ i ∈ N ∑ j ∈ N c i j x i j k s.t. ∑ k = 1 K y i k = 1 ∀ i ∈ N − ∑ k = 1 K y 0 k = 1 ∑ i ∈ N x i h k = ∑ j ∈ N x h j k = y h k ∀ h ∈ N , ∀ k ∑ i ∈ N d i y i k ≤ C ∑ i , j ∈ S x i j k ≤ ∣ S ∣ − 1 ∀ k , ∀ S ⊆ N − , ∣ S ∣ ≥ 2 x i j k ∈ { 0 , 1 } ∀ i , ∀ j , ∀ k y i k ∈ { 0 , 1 } ∀ i , ∀ k minK∑k=1∑i∈N∑j∈Ncijxijks.t.K∑k=1yik=1∀i∈N− K∑k=1y0k=1∑i∈Nxihk=∑j∈Nxhjk=yhk∀h∈N,∀k∑i∈Ndiyik≤C∑i,j∈Sxijk≤|S|−1∀k,∀S⊆N−,|S|≥2xijk∈{0,1}∀i,∀j,∀kyik∈{0,1}∀i,∀k

mins.t.k=1∑Ki∈N∑j∈N∑cijxijkk=1∑Kyik=1∀i∈N− k=1∑Ky0k=1i∈N∑xihk=j∈N∑xhjk=yhk∀h∈N,∀ki∈N∑diyik≤Ci,j∈S∑xijk≤∣S∣−1∀k,∀S⊆N−,∣S∣≥2xijk∈{0,1}∀i,∀j,∀kyik∈{0,1}∀i,∀k

第一个约束条件表示除了起点，每个地点只分配给一辆车；第二个约束条件表示起点出发 K 辆车；
第三个约束条件表示 x x x 与 y y y 的关系；第四个约束条件表示车辆的容量约束；第五个约束条件是子环消除约束。

第三个约束条件也可以写成：

∑ i ∈ N x i h k + ∑ j ∈ N x h j k = 2 y h k \sum_{i\in N} x_{ihk}+\sum_{j\in N} x_{hjk}=2y_{hk} i∈N∑xihk+j∈N∑xhjk=2yhk

网址：旅行商问题，车辆路径问题的数学规划模型 https://www.yuejiaxmz.com/news/view/517793

上一篇：想去的地方很多？用 Tripsy

下一篇：智能旅游线路规划系统设计与实现(