车辆路线问题（VRP）最早是由Dantzig和Ramser于1959年首次提出，它是指一定数量的客户，各自有不同数量的货物需求，配送中心向客户提供货物，由一个车队负责分送货物，组织适当的行车路线，目标是使得客户的需求得到满足，并能在一定的约束下，达到诸如路程最短、成本最小、耗费时间最少等目的。

 

VRP问题有很多子问题：

  • the capacitated vehicle routing problem (CVRP) , 即classical VRP

  • the vehicle routing problem with time windows (VRPTW) , 带时间窗 - VRPHTW 硬时间窗   ｜   VRPSTW 软时间窗   ｜   VRPTD（VRP with Time Deadlines）带顾客最迟服务时间

  • the Multiple Depot Vehicle Routing Problem (MDVRP) , 多车场

  • the Period Vehicle Routing Problem (PVRP) , 周期车辆路径问题

 

一般使用精确算法 或 启发式算法

  • 精确算法适用于小规模问题，能得到最优解。
    • 　direct tree search , 直接树搜索   |   dynamic programming , 动态规划   |   integer linear programming , 整数线性规划
  • 启发式算法用于大规模问题，能快速找出可行解。
    • Simulated Annealing 模拟退火
    • Tabu Search 禁忌搜索
    • Genetic Algoritm 遗传算法    |    Genetic Programming 遗传规划
    • Genetic Network Programming 遗传网络规划
    • ACS, Ant Colony System 蚁群算法

 

我主要是研究了蚁群算法和CW节约算法，发现后者思路比较清晰，并且我们项目的需求也不复杂，所以基于后者的思想来实现。

 

 

考虑这样的需求：

某集散中心管辖10个邮局，已知集散中心和各营业点的经纬度，寄达各支局和各支局收寄的邮件， 时间窗口。

 

 

 

 

 

 

 

 邮车装载邮件数不同。邮车的运行成本为3元/公里， 速度为30km每小时。试用最少邮车，并规划邮车的行驶路线使总费用最省。

 

 

那么输入参数需要包括：

  1. 各个节点的经纬度，邮件收寄数，邮件送达数，时间窗（如果有要求的话，包括最早、最晚到达时间），装卸货时间
  2. 可用车辆的载重

 

输出结果就是算法形成的路径，每条路径中包括到达邮局的先后次序。

 

 

 

目前已经基于CW节约算法，实现 载重量 约束 以及 时间窗口约束，使用Java作为实现。

 

邮局类

 PostOffice.java

 

路径类

 Route.java

 

节约距离类