怎样做百度网站,网站流量是什么,海南开发公司,网站轮播图能用什么软件做目录 前言旅行商问题 (TSP)问题介绍数学模型符号定义问题输入约束条件目标函数问题输出 解的空间解空间大小计算解释 车辆路径问题 (VRP)问题介绍TSP到VRP的过渡数学模型符号定义问题输入约束条件优化目标问题输出 解空间特殊情况一般情况 TSP 与 VRP 对比 前言
计划是通过本文… 目录 前言旅行商问题 (TSP)问题介绍数学模型符号定义问题输入约束条件目标函数问题输出 解的空间解空间大小计算解释 车辆路径问题 (VRP)问题介绍TSP到VRP的过渡数学模型符号定义问题输入约束条件优化目标问题输出 解空间特殊情况一般情况 TSP 与 VRP 对比 前言
计划是通过本文的撰写捋清楚TSP和VRP的本质不同。(什么是本质❔)
对比TSP旅行商问题VRP车辆路径问题描述给定一个城市列表以及每对城市之间的距离访问每个城市一次并返回出发城市的最短路线是什么车队需要向给定的一组客户家中取货需要遍历的最佳路线集是什么输入城市数量距离矩阵城市数量距离矩阵任务量卡车容量约束每个城市仅访问一次每个城市仅访问一次满足容量要求目标最小化总旅行距离最小化总旅行距离输出一个旅行商访问城市的顺序多个车辆的行驶路线空间城市序列 ( n − 1 ) ! (n-1)! (n−1)!城市序列加上车辆任务分配 n ! S P ( n , m ) k n! S P(n,m)^k n!SP(n,m)k
以 n 13 m 5 k 3 n13m5k3 n13m5k3为例对比解空间
TSP解空间 ( n − 1 ) ! ( 13 − 1 ) ! 12 ! 4.79 × 1 0 8 (n-1)! (13-1)! 12!4.79 × 10^8 (n−1)!(13−1)!12!4.79×108VRP解空间 下限 n ! 13 ! 12 ! 6.23 × 1 0 9 n! 13! 12! 6.23 × 10^9 n!13!12!6.23×109上限 P ( n , m ) k P ( 15 , 5 ) 3 3.68 × 1 0 15 P(n,m)^kP(15,5)^3 3.68 × 10^{15} P(n,m)kP(15,5)33.68×1015
旅行商问题 (TSP)
问题介绍
旅行商问题英语Travelling salesman problem, TSP在1930年被首次提出是优化领域研究最深入的问题之一。问题的表述是“给定一个城市列表以及每对城市之间的距离访问每个城市一次并返回出发城市的最短路线是什么” 图片来源algorist.com
数学模型
符号定义 n n n: 城市的数量。 c i j c_{ij} cij: 从城市 i i i 到城市 j j j 的距离或成本。 x i j x_{ij} xij: 决策变量。如果旅行商从城市 i i i 直接前往城市 j j j则为 1否则为 0。
问题输入
城市数量 n n n距离矩阵 c i j c_{ij} cij表示从城市 i i i 到城市 j j j 的距离或成本对所有 i , j 1 , 2 , . . . , n i, j 1, 2, ..., n i,j1,2,...,n 且 i ≠ j i \neq j ij。
约束条件
每个城市只访问一次 ∑ j 1 , j ≠ i n x i j 1 ∀ i 1 , 2 , … , n \sum_{j1, j \neq i}^{n} x_{ij} 1 \quad \forall i 1, 2, \ldots, n j1,ji∑nxij1∀i1,2,…,n ∑ i 1 , i ≠ j n x i j 1 ∀ j 1 , 2 , … , n \sum_{i1, i \neq j}^{n} x_{ij} 1 \quad \forall j 1, 2, \ldots, n i1,ij∑nxij1∀j1,2,…,n
$$
\sum_{j1, j \neq i}^{n} x_{ij} 1 \quad \forall i 1, 2, \ldots, n
$$
$$
\sum_{i1, i \neq j}^{n} x_{ij} 1 \quad \forall j 1, 2, \ldots, n
$$目标函数
最小化总旅行距离或成本 min ∑ i 1 n ∑ j 1 , j ≠ i n c i j x i j \min \sum_{i1}^{n}\sum_{j1, j \neq i}^{n} c_{ij} x_{ij} mini1∑nj1,ji∑ncijxij
$$
\min \sum_{i1}^{n}\sum_{j1, j \neq i}^{n} c_{ij} x_{ij}
$$问题输出
访问城市的顺序。
解的空间
旅行商问题的解空间是指所有可能的路径组合数量。
解空间大小计算
对于 n n n 个城市的 TSP旅行商从一个城市出发并有 ( n − 1 ) (n - 1) (n−1) 个城市可以选择作为第一站。在访问了第一个城市后剩下 ( n − 2 ) (n - 2) (n−2) 个城市可以选择作为下一站以此类推。最后旅行商将从最后一个未访问的城市返回起始城市。
因此TSP 的解空间大小为所有可能路径的数量计算公式为 ( n − 1 ) ! (n - 1)! (n−1)!
其中 ( n − 1 ) ! (n - 1)! (n−1)! 表示 ( n − 1 ) (n - 1) (n−1) 的阶乘即 1 × 2 × 3 × … × ( n − 2 ) × ( n − 1 ) 1 \times 2 \times 3 \times \ldots \times (n - 2) \times (n - 1) 1×2×3×…×(n−2)×(n−1)。
解释
旅行商可以从任何城市开始但是不同的起点并不会影响各城市在解中的相对顺序。每个路径都可以通过循环移位变换为从特定城市比如第一个城市开始的路径所以实际上只需考虑从一个固定城市出发的路径。
车辆路径问题 (VRP)
问题介绍
车辆路径问题英语Vehicle Routing ProblemVRP在1959年被首次提出是TSP的泛化形式包含TSP问题。问题描述车队需要向给定的一组客户家中取货或是送货需要遍历的最佳路线集是什么 值得一提的是在1959年被提出时论文名称是’The truck dispatching problem’并没有使用Vehicle Routing Problem的表述。在随后十多年的相关研究中也一直没有直接使用VRP这一名词的论文。直到Christofides, N.的论文’The vehicle routing problem’于1976年发表后后续研究普遍采用了VRP的表述。
TSP到VRP的过渡
我们把TSP问题或一个场景表述为一辆空载的卡车从车库或是车场出发城市出发需要到多位客户的家中其它城市取货物待取完所有货物后需要返回车库。这里有一个潜在的假定不管所有客户家中的货物累加和究竟有多大这一辆卡车总能全部纳入到自己的车厢中并继续正常行驶。也就是车辆的运输能力 C C C 大于等于所有的货物量 C ≥ ∑ i q i C \ge \sum\limits_i {{q_i}} C≥i∑qi 其中 q i q_i qi 表述第 i i i 个客户家中的货物量。 但是当面临一辆卡车完不成所有的任务量时也就是 C ∑ i q i C \sum\limits_i {{q_i}} Ci∑qi 就需要多辆车去完成或者是一辆车多次往返。 按照论文The truck dispatching problem. Management science 6, 80–91 (1959)里面的介绍把该条件描述为 C ≪ ∑ i q i C \ll \sum\limits_i {{q_i}} C≪i∑qi 并且文章提出假定一辆车最多只能访问 m m m 个点只有当 m m m 比较大时有研究意义否则的话求解比较容易如下 If m m m is small, optimal sets of m m m points may often be determined by inspection of a map which contains the points and the arcs connecting them. One would look for “clusters of points” and determine by trial and error the order in which they should be traversed, taking care that no loop crosses itself. However, when clusters are not present in sufficient numbers or when m m m is large, this procedure becomes inapplicable. In this case near-best solutions may be obtained by the algorithm in this paper. 如果 m m m 很小最优的 m m m 个点的集合通常可以通过检查包含这些点和连接它们的弧的地图来确定。人们会寻找点的簇集并通过试验和错误来确定它们应该按照什么顺序遍历确保没有回路交叉。然而当簇集数量不足或者 m m m 很大时这种方法就不适用了。在这种情况下可以通过本文中的算法获得近似最优解。 数学模型
符号定义 n n n: 任务点的数量。 P i P_i Pi: 第 i i i 个任务点的位置( i 1 , 2 , … , n i1,2,\ldots,n i1,2,…,n)。 [ D ] [ d i j ] [D][d_{ij}] [D][dij]: 任务点间的距离邻接矩阵( i , j 0 , 1 , … , n i,j0,1,\ldots,n i,j0,1,…,n)。 ( Q ) ( q i ) (Q) (q_i) (Q)(qi): 各任务点的任务量( i 1 , 2 , … , n i1,2,\ldots,n i1,2,…,n)。 C C C: 卡车的容量满足 C max ( q i ) C \max(q_i) Cmax(qi)。 x i j x_{ij} xij: 决策变量。如果任务点 P i P_i Pi 和 P j P_j Pj 被同一辆车辆访问则 x i j x j i 1 x_{ij} x_{ji} 1 xijxji1如果不被同一辆车辆访问则 x i j x j i 0 x_{ij} x_{ji} 0 xijxji0对于所有 i i i, x i i 0 x_{ii} 0 xii0。
问题输入
给定 n n n 个任务点的位置 P i P_i Pi。给定任务点间的距离邻接矩阵 [ D ] [D] [D]。给定任务点的任务量 ( Q ) (Q) (Q)。给定卡车的容量 $C。
约束条件
车辆的起点和终点均是车库 P 0 P_0 P0。每个任务点 P i P_i Pi 除了与车库 P 0 P_0 P0 外最多与另一个任务点 P j P_j Pj 被同一个车辆访问一次。对于所有 i 1 , 2 , … , n i 1, 2, \ldots, n i1,2,…,n有 ∑ j 0 n x i j 1 \sum_{j 0}^{n} x_{ij} 1 ∑j0nxij1。每辆车辆在任何时候的载荷不得超过其容量 C C C。对于车辆在访问任务点 P i P_i Pi 时的载荷量满足以下条件 ∑ i 1 n q i x i j ≤ C ∀ j 1 , 2 , … , n \sum_{i1}^{n} q_i x_{ij} \le C \quad \forall j 1, 2, \ldots, n i1∑nqixij≤C∀j1,2,…,n 其中 q i q_i qi 表示任务点 P i P_i Pi 的任务量 x i j x_{ij} xij 表示车辆是否访问了任务点 P i P_i Pi。
$$\sum_{i1}^{n} q_i x_{ij} \le C \quad \forall j 1, 2, \ldots, n$$优化目标
最小化总行驶距离 D D D min D ∑ i , j 0 n d i j x i j \min D \sum_{i,j0}^n d_{ij} x_{ij} minDi,j0∑ndijxij
$$\min D \sum_{i,j0}^n d_{ij} x_{ij}$$问题输出
各车辆的行驶路线。
解空间
在车辆路径问题VRP中我们考虑除起点和终点外的所有车辆行驶路线。这些路线可以排列成一个由 n n n 个点组成的一维序列 S S S拥有 n ! n! n! 种可能性。
特殊情况
假设 n n n 是 m m m 的整数倍且每辆车必须经过 m m m 个点才能返回车库。此时序列 S S S 只需平均分配给各车辆解空间仍为 n ! n! n! 种。
一般情况
如果每辆车经过的点数在 1 到 m m m 之间解空间的计算变得复杂。
目前尚没有发现计算精确解空间大小的文献 AI 也无法给出确切数字下面是一个粗略的估算方法。
单辆车的最大访问点数为 m m m可能的访问序列数量为排列数 P ( n , m ) P(n,m) P(n,m)。对于 k k k 辆车考虑所有可能的序列组合。考虑到车辆间访问点的重叠实际解空间小于 P ( n , m ) k P(n,m)^k P(n,m)k。
因此解空间的上限估算为 P ( n , m ) k P(n,m)^k P(n,m)k。
TSP 与 VRP 对比
对比条目TSP旅行商问题VRP车辆路径问题问题描述给定一个城市列表以及每对城市之间的距离访问每个城市一次并返回出发城市的最短路线是什么车队需要向给定的一组客户家中取货需要遍历的最佳路线集是什么问题输入城市数量距离矩阵城市数量距离矩阵任务量卡车容量约束条件每个城市仅访问一次每个城市仅访问一次满足容量要求优化目标最小化总旅行距离最小化总旅行距离问题输出一个旅行商访问城市的顺序多个车辆的行驶路线求解空间城市序列 ( n − 1 ) ! (n-1)! (n−1)!城市序列加上车辆任务分配 n ! S P ( n , m ) k n! S P(n,m)^k n!SP(n,m)k
以n13m5k3为例
TSP解空间 ( n − 1 ) ! ( 13 − 1 ) ! 12 ! 4.79 × 1 0 8 (n-1)! (13-1)! 12!4.79 × 10^8 (n−1)!(13−1)!12!4.79×108VRP解空间 下限 n ! 13 ! 12 ! 6.23 × 1 0 9 n! 13! 12! 6.23 × 10^9 n!13!12!6.23×109上限 P ( n , m ) k P ( 15 , 5 ) 3 3.68 × 1 0 15 P(n,m)^kP(15,5)^3 3.68 × 10^{15} P(n,m)kP(15,5)33.68×1015 理解本质区别了吗 啥是本质还是迷迷糊糊的️似乎是还差点又似乎是还差许多。下雪了开心
