车辆路径问题

The vehicleroutingproblem (VRP) is acombinatorial optimizationandinteger programmingproblemwhich asks "What is the optimal set of routes for a fleet of vehicles to traverse inorder to deliver to a given set of customers?" Specifically, the context is that of delivering goods located at a central depot to customers who have placed orders for such goods. The objective of the VRP is to minimize the total route cost.

By:https://en.wikipedia.org/wiki/Vehicle_routing_problem

车辆路径问题（Vehicle Routing Problem, VRP），是网络优化问题中最基本的问题之一，广泛应用在物流配送领域。Figure 1.展示了一个VRP的网络，基本的问题描述如下。

Figure 1. The basic illustration of VRP

photograph source：Wikipedia

设有一集散中心(central depot），配备具有相同特征的K辆车,其中，k=，每个车辆容量为C；有n位客户（customers），每位顾客有其特定的需求量D（demand）。车辆从集散中心出发对客户进行配送服务，最后返回场站。要求所有客户都被配送，每位客户一次配送完成并且其demand被满足，且不能违反车辆容量的限制，目的是使总成本最小，也就是所有车辆行驶路线的总距离最小。

在以上问题的基础上，VRP延伸出了几个变种，这些变种问题各自具有其相关的鲜明特征。VRP的分类和她们之间的联系图，如Figure 2.所示。

1)具有容量限制的VRP问题(Capacitated VRP, CVRP);

2)带有距离限制的VRP(Distance-Constrained-VRP,DVRP);

3)带有时间窗VRP(VRP with Time Windows,VRPTW);

4)带有回程的VRP (VRP with Backhauling, VRPB);

5)带有pickup和delivery的VRP(VRP with Pickup and Delivery,VRPPD);

6)以及她们的组合，VRPBTW和VRPPDTW。

Figure 2. The basic problems of the VRPclass and their interconnections

photograph source：Wikipedia

首先，路径优化的基本结构阐述如下。供与需，是路径优化的一对基本矛盾，然而这对矛盾本身往往并不是路径优化要考虑的，路径优化考虑的是这个矛盾化解的过程中，使用怎样的过程从而使得成本最低。也就是说，路径优化考虑的是如何减小（配送）作业过程所带来的成本；如果仅仅考虑消耗在路上的成本，那么问题就转化为求解最短路问题。

其次，路径优化涉及供需两方，通常一个供，多个需求(demand)，需求通过客户位置(positions)和需求量(quantitydemanded)表示。由此，产生几个矛盾，车的容量C决定了一辆车一次只能服务有限的客户；供（配送中心）与客户，以及客户与客户之间，是有路径成本的。当客户及其需求较多的时候，一辆车一车货是满足不了所有客户的，那么就需要一辆车跑多次（圈）或者多辆车各自跑各自的客户（圈）。

因此，路径优化问题可以体现在以下两个方面。

【1】每辆车服务的客户集合；

【2】每辆车服务这些客户的顺序。