物流企业配送车辆调度问题研究综述

1 引言

在竞争日益激烈的现代商业信息社会,企业只有以市场为核心去适应不断变化的环境并及时对市场做出反应,才能在竞争中立于不败之地。物流管理正是以实现上述要求为目标。合理使用调度运输工具,优化运输路线,降低企业物流成本,是物流管理的重要功能。由于对物流管理中的车辆调度问题的研究对社会经济发展具有举足轻重的作用。因此,国内外学术界对物流运输系统的调度优化问题十分关注。配送是物流系统的一个重要环节,配送业务中,配送车辆调度问题的涉及面广,是配送系统优化的关键,具有很大的分析价值。本文正是基于这个原因才对车辆调度问题进行研究。

2 车辆调度问题的概述

物流配送车辆优化调度问题最早是由Dautzig和Ramser于1959年首次提出的,称之为Vehicle Routing Problem(简称VRP)[1]。

VRP问题一般定义为:对一系列给定的顾客(取货点或送货点),确定适当的配送车辆行驶路线,使其从配送中心出发,有序地通过它们,最后返回配送中心,并在满足一定的约束条件下(如车辆容量限制、顾客需求量、交发货时间等),达到一定的目标(如路程最短、费用最少等)。

车辆的优化调度问题主要探讨:组织的行车路线,能否使车辆在满足一定的约珠海到平顶山物流束条件(如需求量、发送量、车载容量限制、行程限制、时间限制等)下,有序地通过一系列供应点或需求点,达到诸如路程最短、费用最小,耗费时间尽量少等目的[2-3]。

自VRP被提出之后,人们在解决VRP问题的时候,综合考虑多方面的因素,如有无时间限制、纯装纯卸或是混合装卸、是满载或是非满载、车型是单车型或是多车型、是单配送中心或是多配送中心以及车辆配送完是不是必须返回原始配送中心等。

2.1 车辆调度问题的分类[4]

车辆调度问题可以细分为 VSP(Vehicle Scheduling Problem,即车辆调度问题)和MTSP(Multiple Traveling Salesman Problem,即多旅行商问题)。但是按照大多数人的习惯,对这几类问题不做严格细分,仍统称为车辆调度问题(即VRP问题)。

车辆调度问题可以根据不同性质划分为以下几类:

有无时间限制问题,即我们所说的有时间窗车辆调度问题和无时限车辆调度问题,是指配送货是否必须在一定的时间限制内完成。对有时间窗的车辆调度问题又可以分为硬时间窗问题和软时间窗问题。而硬时间窗问题是指运输任务必须在规定的时间内完成;软时间窗问题是指任务不一定非得在规定的时间内完成,但是超过规定的时间,则会受到一定的处罚。

纯装问题或纯卸问题,即车辆在所有任务点装货或卸货,即集货或送货问题;而装卸混合问题,则是指每项任务有不同的装货点和卸货点,即集货、送货一体化问题。

满载问题,即货运量不小于车辆容量,完成一项任务需要不只一辆车;而非满载问题,则是指货运量小于车辆容量,多项任务用一辆车。

单配送中心问题和多配送中心的问题,则是考虑客户与配送中的距离长短,以便节约企业运输成本、提高运输效率。

单车型问题即所有车辆容量相同,而多车型问题即执行任务的车辆容量不全相同。

车辆开放问题即车辆可以不返回其发出车场,而车辆封闭问题是指车辆必须返回其发出车场。

综上所述,车辆调度问题涉及的内容较广,包括中国邮递员问题、旅行商问题、指定两点之间的最短距离以及任意两点之间的最短距离等问题,所以研究起来较复杂。

2.2 VRP研究动态及水平

车辆调度问题自被提出来以后,近二十年来,无论是国外还是国内,它都是一个发展活跃的一个领域。在国外,VRP问题已经广泛的应用于实际生活,如邮局的邮件递送业务、超市的商品供应、牛奶站的牛奶送达业务、工业产品的传输、快递公司的运输安排,并取得了很大的经济效益。

VRP问题自从被提出以来,由于其应用的广泛性和经济上的重大价值,一直受到国内外学者的广泛关注。在经典VRP的基础上,车辆路径问题在学术研究和实际应用上产生了许多不同的延伸和变化型态,包括TSP(可看作VRP的一个特例,即当VRP只包括一条路径,且没有能力约束时就成为TSP)、带时间窗的车辆路径问题 (Vehicle Routing Problems with Time Windows,VRPTW)、,随机需求车辆路径问题 (Vehicle Routing problem with Stoehasti Demand,VRPSD)、动态车辆路径问题(Dynamic vehicleRouting Problems,DVRP)等[5-6]。早在60年代Clarke和Wright就提出的节约法 (Saving Method)。1962年,Balinski等人首先提出VRP的集分割,直接考虑可行解集合,在此基础上进行优化,建立了最简单的VRP模型。1971年,Eifon等人提出将动态规划法用于固定车辆数的VRP,通过递归方法求解。其后,Christofields提出了状态空间松弛,极大地减少了状态数量。1974年,Gillet和Miller提出的扫描法(Sweeping Method)。1981年,Christofides等人提出了k度中心树和相关算法,对固定车辆数m的m一TSP进行k度中心树松弛。后来,M.LFisher对这种方法做了进一步改进,可求解有134个客户的VRP。1991年,Gendrean等人[8],将禁忌搜索方法应用于VRP。其后E.Tailiard等人[9]。通过按角度和路径重心对原问题的空间进行分割,再用禁忌搜索结合模拟退火对子问题求解,实现了对问题求解的并行化。1996年,J.Lawrence[10]将遗传算法用于VRP的研究,并可有效求解带时间窗口的VRP。

此外,国外从实用化角度开展的研究也比较多,研究者将模型和算法方面取得的进展应用于很多具体问题。也由此诞生了一些为企业车辆路径提供服务的专业化公司,开发了各具特色的车辆路径软件,比较著名的有:美国ES班公司的Aiclogisties系统,Roadnet科技公司的Roadnet5000系统,Routesmart科技公司的Routesmart系统,Optrak软件公司的OPtrak系统,IBM的VSPX系统,美孚的HPCAD系统,另外还有日本富士通的VSS系统等。

国内VRP的研究起步较晚,国内也有一些对车辆调度进行的研究。李大卫等以TSP的最近距离启发式算法为基础,通过设置评价函数来处理时间窗约束,求解了简单的VRP[7]。张震针对单车场满载问题,提出了考虑运输行程约束的优化方法。蔡延光等应用并行禁忌搜索算法和模拟退火算法对满载问题进行了求解[20]。刘浩等用模拟退火算法求解了两车型随机需求的VRP[11]。张涛等用禁忌搜索算法和遗传算法的混合策略求解了VRP[20]。王莉用启发式算法求解了有时限的VRP[13]。袁健等用神经网络法求解了VRP[14]。姜大立、李大卫分别用遗传算法求解了无时限和有时限的物流车辆调度问题。近年来,郭耀煌、李军、谢秉磊等对物流车辆调度问题进行了较为深入的研究,提出了多种求解算法。周双贵对物流车辆调度问题的模型和求解方法也进行了较为深入的研究[19]。

2.3 车辆调度的目标

车辆调度的目标是以尽量少的路径距离、费用消耗、时间消耗和所需车辆数来可靠地完成汽车调度和货物配送任务。

3 车辆调度问题的研究方法

车辆调度问题的求解算法包括精确算法和启发式算法两个类别。由于车辆调度问题是NP-hard问题,存在高效的精确算法的可能性不大。因此,学者们主要将精力集中在构造高质量的启发式算法上。

3.1 精确算法

精确算法是指可以求出其最优解的算法,主要有:

1) 分枝定界法

此方法是一种隐枚举法或部分枚举法,它不是一种有效算法,是枚举法基础上的改进,是求解整数规划的较好方法。Kolen曾利用此方法求解有时间窗约束的车辆巡回问题,其实验的节点数范围为6~15。当节点数为6时,计算机演算所花费的时间大约1分钟,当节点数扩大至12时,计算机有内存不足的现象产生,所以分枝定界法比较适用于求解小型整数规划问题。Held和Karp指出分枝定界法的求解效率与其界限设定的宽紧有极大的关系,所以分枝定界法比较适用于求解小型问题。

2) 割平面法

此方法与分枝界限法类似,也是在求解与整数规划相对应的线性规划上,不断地增加新的约束,也就是另外加入线性约束条件,以切掉对应于非整数规划的所有可行解的集合,以使问题可达到整数线性规划求解的形式,从而获得最优解。求解时间过长,不适用于大规模问题。

3) 动态规划法

该算法解题的基本思路是将一个n阶段的决策问题转化为依次求解n个具有递推关系的单阶段的决策问题,从而简化计算过程。因其复杂性在于各阶段决策之间的相互联系,而且计算时间与计算机内存空间均随变量的增加而里指数增加.所以虽然此方法可求得最优解,但仅适用于较小规模的寻优问题。第一个VRPTW最优化算法是Kolen等在1987年提出的动态规划算法。

精确算法的计算量随着车辆优化问题规模的增大呈指数增长,如当停车卸货点的数目超过20个时,采用一般的精确算法求解最短配送路径的时间在几个小时以上。所以精确算法不适合于求解大规模的车辆路径优化问题。

3.2 启发式算法

3.2.1 传统启发式算法

传统的启发式算法在求解VRPTW问题时通常是从初始解出发,以邻域搜索的方式实现解的改进,并在较短的时间内获得一个可以接受的解。

1) 节约算法(Saving Method)

算法思想是将每条路线只含一个配送点的n条路线作为初始解,其中,每条路线中第一个和最后一个配送点分别称为路线的起点和终点。考察一条路线的起点与另一条路线的终点相连合并成新的一条路线。如果合并后的路线满足约束条件(车辆容量、时间窗),则认为这样的合并是可行的,并将合并的节约值定义为连接这两条路线的边的节约值。选择节约值最大的可行合并进行一次路线的合并。当不存在可行合并时,算法结束。此方法的优点是可提高车辆的利用率。

2) 邻接算法(Nearest-Neighbor)

邻接算法是一种序列构造路线法。算法从一条只含一个配送点的路线出发(通常取“距离”配送中心最近的点)。在未分配点中筛选出可加入点(未分配点且可行),并从可加入点中选取一个点作为当前路线的终点,使得路线的成本最小。如此不断对路线进行扩充,直到路线不存在可加入点为止。这时,如果所有点均已分配,则算法结束;否则,生成一条新的初始路线,重复前面的路线扩充程序。

3) 插入算法

插入法是结合邻接算法与节约算法的观念,依序将顾客点插入路径中以构建配送路线。它的流程与邻接算法相似,也是从初始路线出发,序列构造路线。并在不存在可行插入时新增一条初始路线。插入算法的关键是选择最合适的未分配点在路线中进行最佳位置的插入。

4) 扫除算法

扫除算法是一种“先分组后路线”的算法。所谓分珠海到通化物流组,即指分派给每辆车一组点。一种简单的分组方法是将以车站为原点的坐标平面划分为多个扇形区域,并初步将每个扇形区域的点分派给一辆车。而所谓的“路线”,是指在每个区域内,采用扫除法选择未分配点,然后应用插入算法扩充路线。如果在进行了一次“分组――路线”的路线构造后,还存在未分配点,则再进入“分组――路线”程序。如此反复,直到所有点均已分配为止。

3.2.2 现代启发式算法

相对于传统启发式算法,现代启发式算法不要求在每次迭代中均沿目标值下降方向,而允许在算法中适当接受目标值有所上升甚至不可行的解,其目的是能够跳出局部搜索邻域。

1) 禁忌搜索算法(Tabu Search,TS)

禁忌搜索算法是局部搜索算法的扩展。该算法通过利用一个禁忌表记录已经到达过的局部最优点,并在后面的搜索中,根据某种限制循环的规则和禁忌表中记录的信息在当前搜索邻域中取一个合适的解。

2) 遗传算法(Genetic Algorithms,GA)

遗传算法是借用适者生存规律进行局部搜索改进的一类算法。该算法通过染色体的配对和变异过程实现种群的进化,每一次进化则对应解的一次迭代。当迭代次数达到最大次数限制或群体中的个体无显著差异时,迭代终止。

3) 模拟退火算法(Simulated Annealing,SA)

1996年,Chiang和Russell提出VRPTW问题的模拟退火算法。模拟退火算法实际上是一种随机松弛技巧,它模拟了退火过程。在搜索的初始阶段,算法跳向远点,随着时间的延伸或“降温”,跳跃幅度逐渐减小,最终转向局部搜索下降方法。

4) 蚁群算法(A珠海到江阴物流nt Colony Optimization,ACO)

蚁群算法模拟了蚁群搜索食物的行为。在寻找食物时,蚂蚁会在它所经过的路径通过排放一种外激素(pheromone,在算法中称为信息素)作出标记,排放的量则根据路径长度和食物的等级决定。这些外激素为其它蚂蚁提供信息,并吸引他们前去搬运食物。算法中,首先构造两组相互协作的人工蚁群,其中第一个蚁群用于最小化车辆数,第二个蚁群用于最小化总路长。并以共用解的方式建立协作关系。

4 各种车辆调度优化算法的比较分析

大家知道,各种优化算法都有其一定的不足之处,不然的话也就不会有这么多的优化算法了。各种优化在一定时期、一定的情况下都有各自的优点,都有解决某一类问题的优越性,但随着发展的需要,对优化方法的要求也就越来越高了。下面对上面所述几种优化方法进行比较分析,通过表格的形式来展现各自的特点。

通过表1我们可以看出精确式优化算法求解是最优解,但只适用于小规模的VRP问题,而不适用于求解复杂的VRP问题,求解复杂的VRP问题时费时又费力,且难以实现。

表2是想改善表一中的精确式搜索算法的不足,但没达到效果,解决大规模的VRP问题仍然是费时又费力,但表3中的现代启发式算法就完全不同了,它适用于解决现实生活中的大规模的VRP问题,我们可以根据不同的情况选择不同的现代启发式算法解决问题所遇到的VRP问题。