带时间窗车辆路径问题的最优解

[摘要] 带时间窗的车辆调度问题是物流配送系统的关键之关键，对它的研究越来越重视。本文将建立物流管理中的带时间窗车辆路径问题的模型，并得到此模型的最优解，有一定的实用意义。

[关键词] 带时间窗车辆路径问题物流管理组合优化

一、提出问题

在许多物流配送系统中，管理者需要采取有效的配送策略以提高服务水平、降低货运费用。其中车辆路径问题是亟待解决的一个重要问题，此问题可描述如下：有一个货物需求点（或称顾客），已知每个需求点的需求量及地理位置，至多用K辆汽车从中心仓库（或配送中心）到达这批需求点，每辆汽车载重量一定，安排汽车路线使运输距离最短并且满足每条线路不超过汽车载重量和每个需求点的需求量且必须只能用一辆汽车来满足。带时间窗车辆路径问题（VRPTW， vehicle routing problem with time windows）是在车辆路径问题中加入了客户要求访问的时间窗口，由于在现实生活中许多问题都可以归结为VRPTW来处理，但处理的好坏将直接影响到一个企业的效益和顾客的服务质量，所以对它的研究越来越受到人们的重视，目前对它的求解主要集中在启发式算法上。

20世纪90年代后，遗传算法、禁忌搜索算法、模拟退火算法、人工神经网络算法和动态蚁群算法等启发式算法的出现，为求解VRPTW提供了新的工具。但是，遗传算法存在“早熟性收敛”问题，禁忌搜索算法、人工神经网络算法也存在一些不尽人意的地方，如何针对VRPTW的特点，构造简单、寻优性能优异的启发式算法，这不仅对于物流配送系统而且对于许多可转化为VRPTW求解的优化组合问题均具有十分重要的意义。实际数据表明动态蚁群算法行之有效，不失为一种求解VRPTW的性能优越的启发式算法。

二、问题描述

VRPTW可以描述如下：给定车辆集合V，需求点集合C和有向图 G。此有向图有|C|+2个顶点，顶点1,2,K,n表示需求点，顶点0表示离开时的中心仓库，顶点n+1表示返回时的中心仓库，把顶点0,1,2,3,K,n+1记作集合N。需求点之间及需求点与中心仓库之间的弧记作集合A，并且没有弧开始于n+1点，也没有弧中止于0顶点，每条弧(i,j)对应一个物耗值cij和一个时间值tij。每辆车有一个载货量q，每个需求点有一个需求dj和一个时间窗口[ai,bi]，这个时间窗口说明车辆必须在bi之前到达需求点i，在ai之前车辆虽然可以到达需求点i，但是车辆必须等待而不可以马上为需求点提供服务。中心仓库也有一个时间窗口[a0,b0]，这个时间窗口说明车辆在a0之前不能离开中心仓库，并且在b0或之前返回中心仓库。在这里，假设q、ai、bi、di和cij均为非负整数，tij是正整数。

对于每条弧(i,j)(i≠j,i≠n+1,j≠0)和车辆k定义变量xijk:如果车辆k没有从节点i到达节点j，则xijk=0;如果车辆k从节点 i到达节点j，则xijk=1。

对于每个需求点i和车辆k定义变量sik，它表示车辆k在sik开始对需求点i进行访问，如果车辆k不访问需求点i，则sik不表示任何意义。假设a0=0，这样对于所有的车辆k，s0k=0。对于每辆车，设计一条费用最小的路径，此路径开始于顶点0，终止于顶点 n+1，同时还要保证每个需求点仅被访问一次，但是不能违背各时间窗口和车辆的载货量的限制。

三、建立模型

根据上述描述，VRPTW的数学模型可以表示为：

在上述表达式中，约束条件式（2）表达了每个需求点仅能被访问一次;约束条件式（3）表达了被调用的车辆都满足能力约束条件;约束条件式(4）和约束条件式(5)保证了每辆汽车始于中心仓库，访问需求点后，最终回到中心仓库;约束条件式(7)表达了车辆k在从i需求点向j需求点行驶的过程中，在sij+tij之前不能到达需求点j，其中k是一个比较大的标量;约束条件式(8)表达了在车辆的行驶过程中，要满足时间窗的约束;约束条件式(9)是整数化的约束。

这个模型的通用性很强，经过参数的不同设定，可以将其转换为其他组合优化问题的数学模型。如果设 ai=0,bi=M(M是一个很大的数），则可以把时间约束式(7)去掉，这样，VRPTW模型就转化为普通的车辆路径问题模型；如果仅有一辆车被利用，则该问题转化为了旅行商问题；如果有多辆车被利用，并且附加条件c0j=1,j∈C和cij=0，就得到了装箱问题的数学模型。如果去掉约束条件式（2），则该模型变成了基本的有时间窗和能力约束的最短路径问题，由于所有的车辆均相同，所以每辆车的最短路径也是相同的。

四、 数值计算结果

有8个分店和一个配送中心，各分店的需求量为dij(i=1,2,K,8)(t)装货(卸货)时间Ti(h)以及分店要求的服务时间范围[ai,bi]由(表1)给出。这些分店由容量为8t的车辆完成配送，配送中心与各分店的距离(km)由(表2)给出。要求合理安排车辆的行驶路线，使总的运距最短。

计算结果见(表3)，可见，运用动态蚁群算法求解的结果优于节约算法、分派算法和遗传算法，不失为一个较优化的满意解。

五、结束语

车辆路径问题已经被广泛的应用到生产、生活的各个方面，如报纸投递及线路的优化及线路设计、垃圾车的线路优化及垃圾站选址优化等等。目前，研究水平已有很大发展，其理论成果除在汽车运输领域外，在水运、航运、电力、工业管理也有一定的应用，还用于轮船公司运送货物经过港口与货物安排的优化设计、交通车路线安排、多种组合优化问题中。车辆路径问题是物流配送优化中关键的一环，也是电子商务活动中不可缺少的内容。对货运车辆进行优化调度，可以提高物流经济效益、实现物流科学化。对货运车辆优化调度理论与方法进行系统研究是物流集约化发展、建立现代调度指挥系统、发展智能交通运输系统和开展电子商务的基础。