带时间窗的车辆路径规划问题(VRPTW)
发布网友
发布时间：2024-10-04 09:17
共1个回答
热心网友
时间：2024-10-04 10:02
车辆路径规划问题（VRP）通常指的是：针对一系列发货点和收货点，组织调用一定数量的车辆，规划适当的行车路线，使车辆有序地通过这些点。在满足特定约束条件（如货物需求量、交发货时间、车辆容量限制、行驶里程限制、行驶时间限制等）的情况下，力求实现一定的目标（如车辆空驶总里程最短、运输总费用最低、车辆按一定时间到达、使用的车辆数最小等）。
带时间窗的车辆路径规划问题（VRPTW）是VRP的一种扩展，它在VRP的基础上增加了配送时间约束条件。在这类问题中，给定车辆到达目的地的最早时间和最晚时间，要求车辆必须在规定的时间窗内到达，早于最早时间或晚于最晚时间都会产生额外的惩罚费用。决策的目标是规划调度车辆，使得配送的总费用最小化。
本文将要研究的问题参考自《Fruit and Vegetable Agricultural Products Logistics Transport Routing Optimization - A Case Study of Qingdao blueberries distribution》一文中描述的案例。案例中，某果蔬农产品运输配送中心C0（Center）拥有足够的能力满足顾客对果蔬农产品数量的需求。配送中心有足够多且完全相同的车辆J来完成配送活动，运输车辆的最大容量为V（Volume）。C={C0, C1, C2, ……, Cn}，其中C0代表配送中心，Ci（i=1, 2, ……，n）表示有需求的客户的需求数量；n表示有需求的客户数量。Dik（Distance）表示顾客Ci到顾客Ck的距离（其中i不等于k）；Qdi（Quantity Demanded）表示顾客Ci的需求量；Qg（Quality good）表示果蔬农产品刚刚采摘完，完好时的质量；[ETi, LTi]表示客户Ci对某类产品的时间窗约束。
在已知以上条件的情况下，合理安排最优的配送路线，使得配送过程中满足所有条件情况下，各个费用之和最少。
本文采用禁忌搜索算法（Tabu Search，TS）作为解决VRPTW问题的方法。禁忌搜索是Glover教授于1986年提出的一种亚启发式随机搜索算法。它从一个初始可行解出发，选择一系列特定搜索方向作为试探，选择实现让特定目标函数值变化最多的移动。逐步迭代，以逼近最优解。为了避免陷入局部最优，TS搜索中采用禁忌表的方式，对已经进行的优化过程进行记录和选择，从而指导下一步移动搜索的方向。
本文采用的编码方式为节点编号的全排列形式，编码与解码如下所示（以7个节点为例）：相应的邻域为节点编号的全排列。本文中采用的邻域动作为1-opt操作算子，如下所示：
图a
图b
图a表示初始解为0-2-3-0，0-4-5-0，0-1-7-6-0，车辆数目为3，1opt算子是将随机选取的节点（图中为1号节点）插入另一条车辆路径中，以形成新的解，图b表示邻域操作之后生成的新的解，虚线表示新的路径，新解即为0-2-3-0，0-4-5-1-0，0-7-6-0。
相关算例与参数均采用原文章算例。节点包括青岛、烟台、东营、泰安、潍坊、日照、枣庄、聊城、济南、淄博、德州、滨州、菏泽等城市。以某次运行的结果为例，分析该路线各个成本的表格如下所示，禁忌搜索最终解为：[7, 12], [5, 6, 3], [8, 10], [1, 4], [2, 11, 9]，相关信息如下：
每个车辆的时刻表：
为了更清楚展示最终结果的路线图，笔者利用百度地图API爬取了上述城市的经纬度，并利用Folium工具包将上述结果的路线在地图上进行展示。（文中只考虑两点之间的欧几里得距离）首先需要登录百度地图官网，申请获得密钥，利用如下代码依次获取相应城市的经纬度；然后，将禁忌搜索得到的各条路线用不同的颜色在folium上画出来。最终以网页的形式存储。
文中算例和参数信息均来自文章《Fruit and Vegetable Agricultural Products Logistics Transport Routing Optimization - A Case Study of Qingdao blueberries distribution》。文中关于VRPTW的禁忌搜索代码只给出了相关算法设计，完整Python代码获取：
关于可视化实验结果的Python代码文中已经全部给出，只需改动相应部分即可使用。
