本文作者(崔雪丽 马 良),请您在阅读本文时尊重作者版权。
VRPSTW的混合改进蚁群优化算法
摘 要:软时间窗车辆路径问题(VRPSTW)是VRP的一种重要扩展类型,定义了其惩罚函数并建立数学模型。设计用于求解该问题的混合改进型蚁群算法并求解标准数据库中的紧时间窗实例。经过大量数据测试,获得了较好的效果,并验证了蚁群算法用于求解软时间窗车辆路径问题的成功实现。
关键词:软时间窗车辆路径问题; 蚁群算法; 惩罚函数文章编号:1001-3695(2010)03-0845-04
doi:10.3969/j.issn.1001-3695.2010.03.010
Hybrid improved ant algorithm for VRPSTW
CUI Xue-li?1, MA Liang?2
(1.Dept. of Logistics Management, College of Economy Management, Suzhou University of Science Technology, Suzhou Jiangsu 215011, China; 2.Dept. of Management Science Technology, College of Management, University of Shanghai for Science Technology, Shanghai 200093, China)
Abstract:Vehicle routing problem with soft time windows is a very important extended type of vehicle routing problem. This paper defined penalty function and established mathematical model of VRPSTW. Designed a hybrid improved ant algorithm for solving this problem and solved some Solomon instances with hard time windows. Computational experiments show that this approach is promising in good performances and verify the success of applying ant algorithm in solving vehicle routing problem with soft time windows.
Key words:VRPSTW(vehicle routing problem with soft time windows); ant algorithm; penalty function
带时间窗的车辆路径问题(vehicle routing problem with time windows,VRPTW)[1]是目前人们普遍研究的VRP的一种扩展类型,它是在VRP的基础上增加了客户要求访问的时间窗口,即给定每个客户一个时间范围,车辆对客户的服务时间必须在这个范围内开始。时间窗问题其实又有硬时间窗和软时间窗之分[2]。在以往的文献中,提到的时间窗问题如果没有特别说明,通常都是指硬时间窗车辆路径问题。
VRPSTW,即软时间窗车辆路径问题[3],它允许车辆对客户开始服务的时间早于客户允许的最早开始时间或晚于客户允许的最迟开始时间,但是要给予一定的惩罚。紧时间窗不仅对服务造成很大的局限性,还会因为严格遵守时间窗的限制而增加车辆数导致总费用的增加。软时间窗这种服务方式虽然增加了一定的惩罚费用,但如果能够节省车辆,以此来减少人力、物力,则最终的总费用反而有可能减少。近年来人们对VRP、VRPTW等这些经典车辆路径问题的研究非常多,而目前在国内外公开发表的文献中对VRPSTW的研究和求解还很少。
VRPTW也已被证明为NP-难题,历年来对其算法的研究主要集中在各种智能化启发式算法上。Koskosidis等人[4]、Balakrishnan[5]、Taillard[6]、Ioannou等人[3]曾先后提出VRPSTW的一些实际性定义以及应用禁忌搜索法、最近邻算法等对其进行求解,得到了一系列的结果。
蚁群算法是受自然界中真实蚁群行为的启发而产生的一种模拟进化算法[7],其基本思想就是对真实蚁群协作过程的模拟,每只蚂蚁在候选解的空间中独立搜索解,并在所寻得的解上留下一定的信息素。解的性能越好蚂蚁留在其上的信息素越多,而信息素越多的解被再次选择的可能性也越大。在算法的初级阶段,所有解上的信息素相同,随着算法的推进,较优解上的信息素逐渐增加,算法最终收敛到最优解或近似最优解。蚁群算法目前已被扩展应用到许多问题领域中[8~13],近几年很多学者将其应用于VRP[14~17]、VRPTW等问题的求解,也获得了很好的效果。本文在蚁群算法思想的基础上,结合线路改进算法中的几种邻域局部改进机制设计了VRPSTW的求解算法,计算Solomon问题库中的实例获得了很好的效果,并与VRPTW结果进行了比较和分析。
1 问题描述
VRPSTW的一般提法[3]为:已知有一批客户,每个客户点的位置坐标和货物需求已知,每辆车都从起点(depot)出发,完成运送任务后再回到起点。每个客户只被访问一次,每辆车所访问的需求总和不能超过车辆的负载能力。给每个客户?i一个正常服务时间窗口[e?i,l?i],如果车辆早于e?i或者晚于l?i到达客户i,则由客户给定一个允许服务提前开始的时间lbv?i或者允许延迟开始的时间ubv?i,但必须以给予客户一定的赔偿为条件。问题的最终目标是以最少的总费用完成所有任务,车辆在这些时间内进行服务的情况如图1所示。??
根据VRPSTW定义,现假设惩罚量是违反时间量的线性函数[5],则惩罚函数可定义为
?ce?i:车辆早于时间e?i到达客户i的单位惩罚数;
cl?i:车辆晚于时间l?i到达客户i的单位惩罚数;
P?i:惩罚函数。
假设se?i为对客户i服务的开始时刻,则惩罚函数P?i的公式为
