下载掌阅APP，畅读海量书库
立即打开
令 G =（ V，E ）表示一个完全无向图， V =｛0，1，2，……， n ｝表示图中点的集合， E =｛（ i，j ）， i，j∈V ； i ≠ j ｝表示图中边的集合。点0表示仓库，在仓库有一定数目的容积均为Q的车辆等待运输任务， H =｛1，2，……， K ｝代表车辆的集合，车辆的数目为 K 。 N =｛1，2，……， n ｝代表客户点的集合。每个客户有一个对应的订单，每个订单的大小（产品需求量）为 q i ，订单的可得时间为 r i ，其代表订单的生产（拣选与打包）完成时间。 t ij 为非负数，表示每条边 e =（ i，j ）的成本，其值等于点 i 到点 j 的行驶时间。当一系列订单被装载到同一辆车时，该车辆最早可以离开的时间为订单中最大的可得时间，该时间被称为车辆可得时间。目标函数为最小化所有车辆路径完成时间之和，每辆车的路径完成时间等于其车辆行驶时间与车辆可得时间之和。约束条件如下：
（1）每个订单只能被安排到一辆车中，且该订单不可以被分批次运输；
（2）每个订单的可得时间不能被违反，即每辆车在其所有订单装载后才可以离开仓库；
（3）每辆车必须从仓库出发，至少访问一个客户后返回仓库；
（4）每辆车装载的产品总数量不得超出其容积。
模型中使用的所有变量与参数说明如下：
（1）变量
x ijk 假如车辆 k 访问边（ i，j ）则其值等于1；否则其值等于0，∀（ i，j ）∈E。
y ik 假如车辆 k 装载客户 i 的订单则其值等于1；否则其值等于0，∀ i∈N 。
A k i 车辆 k 到达访问客户 i 的时间。
（2）参数
i，j 客户编号，其值属于 N =｛1，2，……， n ｝；
k 车辆编号，其值属于 H =｛1，2，……， K ｝；
t ij 客户 i 与客户 j 之间的行驶时间；
q i 客户 i 的订单的大小；
r i 客户 i 的订单的可得时间；
该问题的数学模型如下：
式（4-1）表示目标函数，最小化所有车辆路径完成时间之和，其值等于总的车辆行驶时间与总的车辆可得时间之和；式（4-2）表示每个订单必须由一辆车运输送达客户；式（4-3）表示流量守恒约束；式（4-4）表示每辆车的容积不能被违反；式（4-5）表示消除子循环约束；式（4-6）表示每辆车在其最大可得时间的订单装载后才可以离开仓库；式（4-7）表示如果车辆访问一个客户，则该客户的订单必须被装载；式（4-8）和（4-9）为0-1变量约束。
若令所有订单的可得时间为零，则该问题转化为一个纯粹的有容积限制的车辆路径问题（CVRP），CVRP已经被公认为是NP难题，则本章研究的问题亦为NP难题。精确算法难以解决较大规模的算例，故下面提出一种启发式算法来解决该问题。