作者： 于芹作者单位：上海交通大学文献类型：硕士论文基于蚁群算法的物流车辆路径优化问题的研究01车辆路径规划概述03蚁群算法简介02VRP 问题的相关研究04改进的 ACO 及 TSP 求解05CVRP 问题及求解Contents目录1车辆路径问题概述车辆路径规划概述 车辆路径调度问题是由 G Dantzig 首先提出的 , N Christofides 在后来总结深化。 车辆路径问题（ VRP ），主要解决的是派多少辆车走什么样的路线进行运输的问题。具体来讲，就是给定了相互连通的若干有货物需求的顾客点，若干车辆从配送中心出发，完成对所有顾客点的配送任务后回到配送中心，要求所走的路线不能重复，目的是找到最小成本的配送方案。 根据实际约束条件的差异，车辆路径问题种类千变万化，并各具特色。VRPCVRP拓展VRPMDVRPSDVRPVRPTW配送和收集VRPSVRPTSP经典车辆路径问题，其实就是在车辆路径的调度中，仅仅考虑最基本的货车载重量约束 ( 或容量约束 ) 的最一般化的运输问题，即有容量约束的车辆路径问题 (Capacitated Vehicle Routing Problem ）。经典 VRP 要求满足的条件及假设： 经典车辆路径问题 CVRP所有的配送车辆以配送中心为起点并最终回到配送中心1每条配送路径上各需求点的需求量之和不超过车辆的载重量。2每个需求点的需求由且仅由一辆车一次送货满足3CVRP 的数学模型(1)(2)(3)(4)(5)(6)k ：第 k 辆车 ：运输车辆的数量 ：车辆 k 所走的路径的集合带时间窗的车辆路径问题 VRPTW 在很多时候，会要求在一定时间范围内到达顾客点 ( 当然有时配送中心也有时间范围限制 ) ，否则将因停车等待或配送延迟而产生损失。比较而言，时间窗 VRP 除了必须实现经典 VRP 的要求，还要考虑访问时间的限制，这样才能找到合理方案。 软时间窗 VRP ：要求竟可能在时间窗内到达访问硬时间窗 VRP ：必须在时间窗内到达访问VRPTW 的数学模型2VRP 问题的相关研究对 VRP 问题的相关研究求解问题的精确算法分支定界法Laporte 等人利用 VRP 和其松弛形式 T-VRP 之间的关系 , 把T-VRP 转化成了 TSP 的分枝定界算法求解了一般问题动态规划算法将 VRP 问题视为一个 n 阶段的决策问题 , 进而将其转化为依次求解 n 个具有递推关系的单阶段决策问题 .Eilon 通过递归的形式利用动态规划法求解具有固定车辆数的 VRP 问题三下标车辆流方程由 Fisher 等人提出 , 用以求解带能力约束、时间窗口以及无停留时间的 VRP ...
