每天早晨，物流中心门前都有好几辆卡车装好货物等待出发。今天要送货的地方有几十处，哪辆卡车负责哪一家、按什么顺序跑，都得先定下来。即使运的是同样的货、送往同样的人家，路线怎么安排，一天下来行驶的距离、油钱和司机下班的时间都会大不相同。
简单地说，车辆路径问题（Vehicle Routing Problem）是指“多辆车从仓库出发，分头拜访多个客户后再返回时，找出总成本最低的一组路线”的问题。1959年，乔治·丹齐格（George Dantzig）和约翰·拉姆泽（John Ramser）把它作为向加油站运送汽油的卡车调度问题首次提出，如今它已成为快递和流通物流的基本计算。
本文将依次介绍车辆路径问题的基本结构、可能性为何会爆炸式增长、现实中叠加的各种条件，以及求解的方法。
一次性规划多辆卡车路线的计算
车辆路径问题的基本结构
只要确定几个要素，车辆路径问题的面貌就会变得清晰。
（1）仓库与车辆
所有车辆都从同一个仓库，也就是出发基地出发，干完活后再回到那里。有几辆车、每辆车能装多少，从一开始就是确定的。
（2）客户与需求
每个送货地点都有位置和需要收到的货量。每位客户必须恰好被服务一次，而且只能由一辆车送货。
（3）行驶成本
两个地点之间往返所需的距离、时间或费用要事先算好。如果先在真实路网中求出最短路径，各地点之间的成本就可以像一张表那样处理。
（4）目标
最常见的目标是降低总行驶成本。有时也会以车辆数最少，或让每辆车的工作量均衡为目标。
可能性为何会爆炸式增长
一辆卡车绕所有人家跑一圈、找出最短顺序的问题，称为旅行商问题（Traveling Salesman Problem）。车辆路径问题是把旅行商问题扩展到多辆车，所以至少和它一样难。
要访问10个地点的话，光是行驶顺序就有约362万种。到了20个地点，这个数字会膨胀到约243京种。再加上还要决定哪辆车负责哪位客户，把所有情况逐一比较的办法很快就会走到尽头。
数学上把这类问题归为NP-难（NP-hard）问题。意思是随着客户数量增加，求出精确答案所需的时间可能增长得快到无法承受。因此在实际工作中，人们往往选择快速找到足够好的答案，而不是完美的答案。
现实叠加的各种条件
实际的配送现场比教科书里的问题复杂得多，每多一个条件，就会产生一个新的变体问题。
- 载重容量约束（Capacitated Vehicle Routing Problem）：每辆车能装的重量或体积都有限，必须在不超过限度的前提下划分客户。
- 时间窗约束（Vehicle Routing Problem with Time Windows）：每位客户都有可以收货的时间段，必须在这段时间内到达。
- 取货与送货（Vehicle Routing Problem with Pickup and Delivery）：在一处装货、到另一处卸货，两项工作要一并处理。
- 多仓库（Multi-Depot Vehicle Routing Problem）：车辆出发和返回的仓库有多个。
- 电动车路径问题（Electric Vehicle Routing Problem）：同时考虑电池能行驶的距离和充电的地点。
除此之外，还有车辆不必回到仓库的情况、一天多次往返仓库的情况等，随着现场情况的不同，人们研究着各种各样的变体。
求解的方法
求解车辆路径问题的方法大致分为求精确答案的一类和快速求出好答案的一类。
精确解法
先用整数规划这一数学模型把问题建立起来，再巧妙地筛掉可能的情形，找出最佳答案。答案的质量有保证，但客户一多，计算时间就会大幅增加，所以主要用于规模较小的问题。
节约算法
这是1964年由克拉克（G. Clarke）和赖特（J. W. Wright）提出的方法。它先假设每位客户各派一辆卡车单独前往，然后把两位客户连成一条路线时减少的距离，也就是节约量，从最大的一对开始依次合并。计算简单，结果也好用，至今仍被广泛使用。
元启发式算法
遗传算法、禁忌搜索、模拟退火等方法，会把最初构造的路线一点点修改，逐步找到更好的答案。据说近年来表现出色的方法，即使面对数百到数千个地点的问题，也能把与最优答案的差距缩小到1%左右。
车辆路径问题看起来像是在地图上画线，但背后是想同时降低成本、时间和人力劳动的计算。制作路径规划软件的厂商宣称能节省5%至30%的成本，也体现了这种计算的力量。
为了用更短的路把同样的货运出去而不断重新核算路线，这就是高效配送的第一步。
