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】每辆车服务这些客户的顺序。
领取专属 10元无门槛券
私享最新 技术干货