供应链物流配送路径优化节约算法改进研究.pdfVIP

、I 匐 似 供应链物流配送路径优化节约算法改进研究 Studies on improving C-W saving algorithm of the VRPSDP in supply chain logistics 金 成，闵嘉宁 JlN Cheng．MIN Jia．ning (无锡太湖学院，无锡 214064) 摘 要：针对供应链物流配送中的有时间窗约束集送货一体化路径优化问题研究了基于C—W节约算法 的改进算法。提出了以集货量和送货量共同作为客户点归并的判断条件，把时间窗约束转化 为里程，用里程数来控制客户点的归并、插入和时间窗约束的计算，实现了多个目标 (里 程、集送货一体、载重、时间窗)的路径优化；算法在实现中对合并点归并位置进行了深人 研究，根据归并点的特点和约束条件的不同，进行了分别处理，获得了较好的优化结果。该 改进的节约算法有效的减少里程数、用车量，节约了费用、降低了成本。 关键词：改进的C—W节约算法；集送货一体；时间窗约束；路径优化 中图分类号：093 文献标识码：A 文章编号：1 009—01 34(2014)01(I-)一0086—04 Doi：1 O．3969／j．issn．1 009-01 34．2014．01(E)．25 0 引言 完整的物流系统应包括配送物流和集货物流， 集货物流是绿色物流的一个有机组成部分 。集送 货一体的物流广泛应用于电子商务中，可以减少 单集货和单送货情况下车辆 ‘空跑’所带来的消 耗，减少运输成本，降低流通成本，增加企业效 益，已成为物流行业发展的新潮流。 集送货一体的物流中，有效的车辆路径优化 对增加集送效率、减少总费用和提高配送服务水 平起到至关重要的作用。集送货一体的车辆路径 优化问题VRPSDP(Vehicle Routing Problem with Simultaneous Delivery and Pickup) 是对一系列 集送货点，组织适当的行车路线，使车辆有序地 通过它们，并最终返回配送中心；在满足一定的 约束条件 (例如集送货量、集送货时间、车辆载 重量、行驶里程等)下，使得费用最少 (例如里 程最短、油耗最少、时间最少、使用车辆最少 等)。 路径优化问题VRP最早是由Dantzig和Ramser 于1959年提出的。VRP属于NP—hard问题，实际应 用中多采用启发式算法和元启发式算法，其中由 Clarke和 Wright_4 于1964年提出的c—w节约启发式 算法由于概念清晰、容易实现很受企业欢迎。但 是，在实际应用中，往往存在多个约束条件、多 个优化 目标，尤其是集送货一体和时间窗的引入 要求对C—W节约算法进行改进以适应新的需求。 本文以VRPSDP为研究目标，设定送货与集货 均无优先权，实现边配送边集收的运输过程，对 集送货一体带有时间窗的VRP进行建模；对节约 算法进行改进，使得在满足软时间窗的条件下， 里程数最少并尽可能最大程度地利用车辆的载重 能力；通过实例求解验证，说明算法的合理性和 有效性。 1 问题描述及数学建模 VRPSDP问题可以描述为：配送中心及客户以 点i(i=0，1，⋯，n)表示，其中配送中心编号为0，客 户n个；各点位置巳知，di 表示客户i到客户j的之 间的距离；配送中心拥有足够的运载能力且车型 一 样，各货车的载重量为Q，客户i的送货量为wi Q、集货量为P Q(i=l，2，⋯，n)；tij表示车辆从客户 i行驶到客户j的时间，si表示运货车辆到达客户i的 时间 (也即客户i卸／装货任务的开始时间)，Ti为 完成装／卸货任务所需的时间；车辆从配送中心出 发，完成配送和集货任务后装载收集的货物返回 配送中心。目标为：在满足载重约束和时间约束 的前提下求货运的最短行车路线。载重约束为： 一 条线路上客户的总货运量 (集送货量)不大于 货车的载重量Q；时间约束为：运货车辆到达客户 i的时间Si需要在一定的时间范围 [ET ，L T1]内，其 中 ETi为到达的最早时间，L T_为允许的到达的最 收稿日期：2013-10-21 基金项目：江苏省教育厅项 目 (13KJD520009) 作者简介：金成 (1976一)，男，江苏无锡人，讲师，研究方向为物流管理。 [861 第36卷 第1期 2014—01(上) 学兔兔 l 匐 化 迟开始的时间。设决策变量为 J： Xijk= 』 k由点i驶向局 ，Vi,Vj∈{0，l2，⋯川； 10否则 U’I， ：n皇 货运任务由车辆 完成 {0，1，2， 0否则 vj ” 目标函数： minZ=∑∑∑dox拈 S．t． ∑，， ： k ∑ =Y i=0 E乃 sj 乃 ∈{0 71，2，．．，n}； Vk ∈{0，1，2，．．， }； ∑w