智能优化算法VRP概述

车辆路径问题（vehicle routing problem，VRP）是物流配送优化中关键的一环，是提高物流经济效益、实现物流科学化所必不可少的，也是管理科学的一个重要研究课题.该问题自提出以来，很快便引起运筹学、应用数学、物流科学、计算机科学等各学科专家与运输计划制定者和管理者的极大重视，成为运筹学与组合优化领域的前沿与热点研究问题。许多学者对该问题进行了大量的理论研究及实验分析，取得了极大的进展。

VRP问题可以描述如下：在某些限制条件下，设计从一个或多个初始点出发，到多个不同位置的城市或客户的最优送货或路径分配，即设计一个总代价最小的路线集，使得：

（1）每个城市或客户只被一辆车访问一次；

（2）所有车辆从起点出发再回到起点；

（3）某些限制或约束条件被满足。

最常见的约束条件包括：(www.xing528.com)

（1）容量限制。对每个城市i都有一个需求量di，任何车辆所负责解决的需求总量不能超过车辆的负载能力.这种有容量限制的VRP称为CVRP。

（2）总长限制。任何路径（或时间）长度不能超过某一常数，这个长度包括城市间的旅行时间和在城市的停留时间.这种有路长或时间限制的VRP称为DVRP。

（3）时间窗。城市i必须在时间段［bi，ei］中被访问，允许在城市i停留.这种有时间窗限制的VRP称为VRPTW.

（4）两个城市的优先关系：城市i必须在城市j之前被访问。