车辆路线问题的二阶段启发式算法及其在现代物流配送中的应用

发布时间：2020-04-15 03:53

【摘要】：车辆路线问题是管理科学的一个重要研究课题,其优化技术是现代物流配送的一项关键技术。本文对车辆路线问题,以带时间窗的车辆路线问题(VRPTW) 为研究对象提出一种二阶段启发式算法,并设计一种结合路线编辑、算法调整及系统改进的人机交互优化模式;最后对现代物流系统的配送路线问题进行研究。车辆路线问题研究总成本最小的车辆路线,在合适的时间以合适的方式将正确的货物运送到正确的地点。物流配送则要求在正确的时间以正确的方式将正确的货物送到正确的地方。车辆路线问题在物流配送中有着广泛的应用背景。在各种车辆路线问题中,一个基本问题是带时间窗口的车辆路线问题 (VRPTW)。其主要内容是:以成本最小的目标安排多辆车有序地前往配量给定的各配送点而构成的配送路线,其中每辆车必须从同一车站出发并最后返回车站,每个配送点只能安排一个车次在限定的时间窗内配送,且每一条配送路线不得超过车辆的装载容量和车辆的最后返回时间;如果车辆提前到达配送点,则需要等待,直到在时间窗内才能配送。 VRPTW 问题属于 NP-难问题,其算法通常采用了从初始状态出发进行邻域搜索的启发式算法。其中,邻域搜索被定义为以边的替换,或者点的交换或重新定位等为基本操作的搜索。为了使解不过早地陷入局部最优,现代启发式算法引入了禁忌搜索、遗传算法、蚁群算法、模拟退火算法等技术。本文以 VRPTW 问题为研究对象,提出一种二阶段启发式算法。主要内容有: 1)提出一种新的边替换搜索方法。即在搜索的一次操作中替换多条路线的多条边。其中,限制参与边替换的路线条数、每条路线的被替换边数,以及被替换边选自解的一个边子集。其特点是:在边子集中可以考虑所有替换组合;如果选取所有路线的所有边考察其替换选择,则这种搜索方法便是一种穷举优化法。 2)提出一种新的点重新定位搜索方法。即在搜索的一次操作中选取多条路线的多个点,根据最小成本插入法进行重新定位。其中,限制参与点重新定位的路线条数、每条路线的被重新定位的点数,以及被重新定位的点选自一个点子集。 3)应用扫除法原理设计 VRPTW 问题的路线构造算法。算法考虑了车辆和 WP=4 点的优先级配送,并在出现运力不足时用虚拟车辆填补运力缺口。 4)在以上创新性研究的基础上,提出一种二阶段启发式算法。本文应用这种算法,并采用小邻域搜索的参数设置,对国际上公认的标准测试问题进行计算试验。结果显示:应用以上两种搜索方法对初始解有显著改进;将计算试验获得的解与目前世界上公认的最好启发式解相比较,一部分解达到最好启发式解,少部分解的总路长低于最好启发式解的总路长,其它解则接近最好解。这种算法的特点适合人机交互优化。通过人机交互,应用这种算法能够进一步获得更好的解。车辆路线问题是一类非常复杂的优化问题。在配送决策系统中,采用人机交互的方式求解车辆路线问题是非常必要的。本文提出了一种结合路线编辑、算法调整及系统改进的人机交互优化模式。其中,通过点的人工重新定位,进行路线的编辑;通过路线或点的锁定,限制系统改进的搜索邻域;通过各种启发式方法的取舍及其参数设置,调整系统改进的算法。采用这种模式,不但可弥补启发式算法的不足,提高算法的搜索效率,而且可在突发情况下人工参与决策。最后,本文对现代物流系统的配送路线问题,做了以下研究: 1)在不同配送环境不同配送要求下,对 VRPTW 问题的推广进行启发式方法的研究。这些推广包括:多车型、多货舱、多品种、混合装卸、多时间窗、拆分配送、分优先级配送、临时增减配送、跨区域配送、流量分配、运输管制、交通约束、有限运力、有限库存/库容、工作量平衡以及成本的广义定义。 2)研究配送路线决策系统与 GIS 系统以及物流信息系统的数据交换。 3)研究油品配送、零售配送和快递配送的配送路线问题。它们分别属于散装品配送、包装品配送和带时间目标的配送。其中,在油品配送中主要研究了宽时间窗的启发式方法;在零售配送中分析了多仓库配送;而在快递配送中重点研究了快件收取的车辆路线问题,其中提出三个路线决策准则,并进行模拟试验研究。
【图文】：

方法,改变路线,两条路线,路线

图 1.7 第一类型的 3-opt 搜索的边替换方法。图 1.8 第二类型的 3-opt 搜索的边替换方法。pt*，Potvin和Rousseau[121]提出一种两条路线之间的边替换方法——条路线中各取一条边，在不改变路线方向的前提下用新的两条边2-opt*的边替换方法。图中用新的两条边(i, j+1)和(j, i +1)替换两

示意图,原理,示意图,种子点

PTW 问题的路线构造算法法原理扫除法构造车辆路线，是指优先将处于同一方位的点分配给同一辆：对一辆车，首先从未分配点中选取一个种子点（seed node），并，从车站向种子点发出的射线为极轴，将所有未分配点的直角坐标；然后，按极角从小到大（或从大到小）逐个选点插入路线，，直到力极限或其他限制为止(如图 2.1)。
【学位授予单位】：复旦大学
【学位级别】：博士
【学位授予年份】：2004
【分类号】：F250

【引证文献】