车辆路径问题

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】每辆车服务这些客户的顺序。

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180604G00YAX00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券