车辆配送路线优化（精选7篇）
车辆配送路线优化 篇1
►►一、 问题的描述
物流中货物配送 (例如烟草配送、食品配送等) 车辆优化调度是对一系列装货点和卸货点, 在满足一定约束条件 (货物需求量、发送量、交发货时间、车辆容量限制、行驶里程、时间等) 下, 达到一定的目标 (路程最短、费用最小、时间最小、使用车辆最少等) , 而进行组织适当的行车路线。配送是在集货、配货基础上, 完全按照用户要求, 包括种类、品种、数量、时间等方面的要求所进行的运送, 是 “配”和 “送”的有机结合形式。
车辆优化调度问题一般可根据空间特性和时间特性分为车辆线路规划问题和车辆调度问题。当不考虑时间要求, 仅根据空间位置安排车辆的路线时称之为车辆路线规划问题VRP (Vehicle Routing Problem) ;当考虑时间要求安排运输路线时称之为车辆调度问题VSP (Vehicle Scheduling Problem) 。车辆的优化调度问题是一个有约束的组合优化问题, 它是一个非确定型的多项式问题 (NP问题) , 该问题的解有多个, 随着其输入规模的扩大, 问题的求解难度大大增加, 求解的时间呈几何级数上升。目前, 尚无有效的多项式时间算法来求解NP问题。
本文所涉及的问题主要是VRP问题。该问题描述如下:从某物流中心用多辆货物配送车辆向多个客户送货, 每个客户的位置和货物需求量一定, 每辆货物配送车辆的载重量一定, 其一次配送的最大行驶距离一定, 要求合理安排车辆配送路线, 使目标函数得到优化, 并满足以下条件:
(1) 每条配送路径上各客户的需求量之和不超过配送车辆的载重量;
(2) 每条配送路径的长度不超过配送车辆一次配送的最大行驶距离;
(3) 每个客户的需求必须满足, 且只能由一台配送车辆送货。
在求解车辆优化 (配送车次数和所有车次路程总和) 调度问题时, 常常将问题分解或转化为一个或几个已经研究过的基本问题, 如旅行商问题, 最短路径问题, 最小费用流问题等。再用比较成熟的理论和方法进行求解, 以得到原车辆调度问题的最优解或满意解。)
►►二、问题的数学模型
主目标函数:总距离最小
次目标函数:出车次数最少
约束条件:
undefined
(2-2) 限制每辆车的起点和终点都是物流中心, 其他的网点只能服务一次
(2-3) (2-4) 限制一辆车只能一次通过i到j的路径
(2-5) 如果车辆v的路径中存在网点i到网点j的连接, Xijv;否则为0
(2-6) 如果网点i由车辆v配送, 则Yiv=1;否则为0。
►►三、 优化方案的改进
解决VRP问题的一种基本方法为最近邻点法, 该方法的基本原理为:从物流中心出发搜索距离物流中心最近的、未访问的网点作为第一个网点并设为已访问, 然后以该点为中心搜索与之相邻的、未访问的网点, 如果加上该点不会超出容量限制, 则将该点加入到线路中并设为已访问, 否则结束该条线路;重复上述步骤, 寻找距离物流中心的最近的未访问的网点作为新线路的第一个网点, 生成新的线路, 直到将所有的网点都访问过。
传统的最近邻点法方法简单, 但得到的解并不十分理想, 算法划分生成的线路可能造成的不均衡现象一般是最后几条线路由于网点数目少而工作量偏低。
为了更有效地实现优化目标, 对上面的最近邻点法作如下改进:
1.从配送中心开始, 作为整个回路的起点, 寻找距离配送点最远的 (而不是离配送点最近的) 一个尚未访问的结点作为首结点, 然后以该点为中心搜索与之相邻的、未访问且容量不超出车中剩余量的结点。这样可以保证路径的优化, 并且最后几条路线中结点都距离配送中心较近, 避免了最后几条线路由于网点数目少而工作量偏低的情况。
2.为了尽可能地实现每辆车次距离的优化, 从而达到总距离最小, 在一个结点访问后再搜索下一个访问结点时, 可以引入一个距离, 我们称之为“邻接半径”, 用于控制访问下一个结点的访问范围。也就是说, 只对与当前结点距离小于邻接半径的结点进行访问。实验显示, 当邻接半径为配送中心到最远结点距离的四分之一到三分之一时, 总距离优化效果较佳。在实际应用中, 可以按结点的实际颁布情况, 将邻接半径作为参数进行调整。
3.在基于GIS电子地图的车辆调度基础上, 建立车辆调度与送货管理系统, 采用人机交互方式与优化算法的有机结合, 实现对卷烟配送线路的规划调度及优化。通过电子地图, 可以对配送路线进行动态管理, 每次排定送货线路, 计算机自动记录所选定的路线, 形成历史记录, 以便于调用和参考。管理系统还能与基于GPS/GPRS的车辆定位系统对接, 随时监控车辆运行和安全情况, 实现货物配送的有效管理, 降低配送成本。
►►四、算法及其实现过程
根据以上讨论, 可以给出算法实现的具体步骤如下:
1.建立货物需求信息及车辆信息数据库。数据主要包括:货物需求用户的编号 (结点号) , 各结点号的需求量;各车子的编号、装载量及最大行驶距离等。
2.采用GIS电子地图、GPS/GPRS的车辆定位系统, 结合弗洛伊德 (Floyd) 算法, 采用人机交互方式确定得到任意两个结点之间的最短路径, 并确定邻接半径。
3.选定一辆车, 以配送中心 (结点编号为0) 为起点, 寻找距离配送点最远的一个尚未访问的结点, 如果运载量大于结点的需求量, 标记该结点为已访问的当前结点, 并将该结点加入当前车辆运载线路中, 当前车量的运载量减去当前结点的需要量。
4.以已访问的当前结点为中心, 搜索与之距离不超过邻接半径且需求量不超出当前车辆运载量的尚未访问的最近结点, 同时要求车辆行驶到该结点为止的行车路线与该结点到配送中心距离之和不超过该车辆的最大行驶距离。如果存在这样的结点, 则将该结点标记为已访问的当前结点, 并将该结点加入当前车辆运载线路中, 当前车量的运载量减去当前结点的需求量;如果不存在这样的结点, 则结束本条路线, 并依访问次序的逆序输出本条线路。
5.重复上述第3、4步骤, 直到所有结点都已被访问。
►►五、结论
货物配送路线优化方案的优劣, 取决于数学模型与现实情况的符合程度以及对数学模型求解的精确程度这两个因素的共同作用。若追求数学模型与现实状况完全符合, 则所建立的数学模型必定非常复杂, 无法求出最优解; 若数学模型建立得太简单, 虽然易解, 但会与现实情况偏差太大, 无实际意义。因此, 应该使之尽量和谐, 找到二者的临界点, 才能搜索到最优的配送路线。
实验结果显示, 改进之后的最近邻点法, 与原来的最近邻点法相比, 总的距离和出车凑数都有所减少, 达到了节约成本的目标。但由于最近邻点法数学模型相对简单, 在实际应用中, 若要考虑时间的约束、线路拥挤程度等等因素的VSP时, 则可以将由最近邻点法得到的结果作为问题的初始解, 然后采用其它算法, 进一步求精。
摘要：本文阐述了货物配送方案中采用最近邻点法进行车辆路线优化的设计方案, 给出了改进的最近邻点法优化思想和实现方法。实验结果表明, 改进的法算法比传统的配送方案减少了出车次数和总路程, 降低了成本, 实现了对货物配送的有效管理。
关键词：车辆路线规划问题,最近邻点法,弗洛伊德 (Floyd) ,算法
参考文献
[1]秦明森、言木.物流决策分析技术[M].中国物资出版社, 2003.9
[2]汪寿阳、赵秋红, 夏国平.集成物流管理系统中的定位——运输线路安排问题的研究[J].管理科学学报, 2000, 3 (2)
[3]徐业昌.基于地理信息系统的最短路径搜索算法[J].中国图象图形学报, 1998 (1)
[4]葛元君、李明秋.基于GIS的现代化物流配送系统的探讨[J].物流技术, 2003 (4)
物流配送车辆优化调度问题概述 篇2
配送是以用户需求为前提,对货物进行挑选、包装和分配等一系列工作,并将其送至指定地点的活动。配送是物流活动的核心环节,需要完成货物的包装、保管、运输和装卸等多项任务。配送的基本要求是保证货物的种类和数量没有差错,在此基础上保证能够按时送达客户。在实现这两个保证后,力争寻求到更加节约成本且更为快捷的配送方案,以实现利益的最大化。而在整个物流配送环节中车辆调度问题最为重要,与经济效益密切相关。
从1959年首次提出物流配送车辆优化调度问题直至发展到今天,物流配送行业一直致力于在满足一定约束条件下(包括用户需求和现实因素的限制等),选取最为合适的行车路线,争取最大面积覆盖取送货点,优化各项指标,最终实现效益的不断攀升。
2 车辆优化调度问题概述
车辆优化调度问题根据时间特征的差异可分为车辆调度问题VSP(Vehicle Scheduling Problem)、车辆路径规划问题VRP(Vehicle Routing Problem)以及有时间窗的车辆路径问题VRPTW(Vehicle Routing Problem with Time Windows)。其中VSP问题侧重于考虑时间上的要求来安排运输线路;VRP问题不考虑时间因素,仅从空间上对问题进行优化,目的在于令安排的路线更加合理;此外,由于VRP问题的不断发展,在原本根据空间来安排路径的基础上,加上时间上的排程考虑,便成为有时间窗的车辆路径问题VRPTW,特点在于在车辆途程问题之中加入时间窗的限制。
也可进行如下分类:
(1)按送货计划安排分为纯装问题、纯卸问题和装卸混合的问题。区别在于安排纯装问题和纯卸问题的车辆允许在所有任务点装货或卸货。而装卸混合问题比较复杂,装货和卸货可能同时进行,并没有严格界定。
(2)按车辆的装载货物量分为满载问题和非满载问题。安排满载的车辆完成任务时可能需要多辆车,而安排非满载的车辆完成任务时,多项任务仅需一辆车就能完成。
(3)按车辆类型分为单车型问题和多车型问题。单车型要求完成此次任务的所有车辆,其容量完全相同,而多车型并没有此要求,可以搭配安排。
(4)按优化指标多少分为单目标优化问题和多目标优化问题。单目标优化问题仅要求一项指标最优,通常这项指标是该次任务最为重要的指标,而多目标优化问题将考核目标范围扩大,要求多项指标最优或较优,如既要求路途短,又要求运费少。
(5)按时间窗要求分为硬时间窗问题、软时间窗问题。硬时间窗要求车辆必须完全遵照时间安排,早到必须等待,而晚到则拒收。而软时间窗相对灵活一些,可以不在时窗内到
3 车辆优化调度问题研究
车辆优化调度问题可通过精确算法和启发式算法来进行求解。精确算法是根据问题建立数学模型,然后进行求解,具体方法都有割平面法、线性规划法、动态规划法等,精确算法由于设计过于理想,并不具有普遍适用性。启发式算法结合直观情况和经验,是一种逐步逼近最优解的算法,具体方法有构造算法、神经网络法、遗传算法等,启发式算法更为接近实际生活情况,适用范围广泛,正是我们研究的重点所在。
在此介绍几种常用的优化算法:
3.1 遗传算法
J.Holland教授于1975年首次提出遗传算法(Genetic Algorithm,GA),遗传算法源于物种进化的自然选择理论,结合物种进化过程中适者生存规则以及染色体中随机信息的交换,发展形成的一种智能算法。遗传算法的基本思想是:从群体中选择较为适应环境的个体用于繁殖下一代,对选中个体进行交叉、变异等操作,以适应度为选择原则,通过算法的迭代选取最优个体。当最优个体的适应度不再变化时迭代结束,得到全局最优解。遗传算法广泛应用于多项领域,属于智能计算的关键技术。
优点是具有鲁棒性,全局搜索能力强,耗时较短,但是不能保证每次搜索结果一样。
3.2 模拟退火算法
N.Metropolis于1953年首次提出模拟退火算法(Simulated Annealing,SA),模拟退火算法的基本思想是:首先,给定一个初始状态,并设定初始温度和降温次数,同时在邻域范围求出另一个解,结合控制参数选择接受或舍弃,经过反复实验后,求得参数控制下的相对最优解;下一步,构造降温函数,不断减小控制参数的值直至为0,此时获得的解即为全局最优解。前半部分是通过加热增加物体能量;后半部分是通过降温来减少物体的能量。对照数学模型,所构造的目标函数就是物体的能量,故求最优解的过程就是求能量最低态的过程。
优点是有很强的全局搜索能力,但是由于允许移动到较差的解,所以会出现接受目标值不好的状态,仅产生局部最优解,导致求得全局最优解要花费较长时间。此外模拟退火的有效性与邻域的选择相关,若邻域的设计范围合理,算法将更为优越,反之,会影响获得的结果。
3.3 蚁群算法
M.Dorigo于1992年首次提出蚁群算法(Ant Colony Algorithm,ACA),蚁群算法源于蚁群在觅食时发现最短路径的行为,蚁群通过寻找信息素浓度最高的路径,从而找到最佳路径,蚁群算法是一种模拟进化算法。蚁群算法的基本思想是:首先,将多只蚂蚁分别放在不同的初始点处,设定顶点也置于当前解集中,蚂蚁从初始点开始转移,直到所有的点都已存在于解集中,得到各只蚂蚁的适应度,记录下当前最优解;然后更新信息素,迭代结束后,求出种群进化后的最优解,便得到问题的最优解。
优点是求解结果不依赖于初始线路,且不需要人为参与调整,设置较为简单,但需要不断调整变量,过程繁琐,任务量大。
4 当前研究中存在的问题
当前对于物流配送车辆优化调度问题的研究,模型设计比较简单,而且将影响因素孤立开来,使得构造的模型与现实复杂的情况出入较大。其次,典型模型的设计与实际情况不符,如典型模型默认是集货送货一体化的问题。实际上,大部分物流公司的业务是集货任务、送货任务、集送一体化任务混合在一起的,在物流配送中需要综合考虑,统一安排车辆。另外,在模型的设计中并未考虑到一些突发情况,过于公式化,导致在实际应用中比较局限。
5 车辆优化调度问题研究展望
针对当前研究中存在的问题,要想把研究真正与实际相结合,更具有应用价值,应该注重对研究问题的描述,建立与实际情况相符合的模型。其次,鉴于道路交通状况对调度的影响越来越大,将实时交通状况与车辆调度问题相结合是十分有必要的。
物流业和配送业近几年在我国迅速崛起,车辆优化调度问题也日益重要。但是由于我国在这方面起步晚,发展速度缓慢,无法满足日益增长的需求。同时对于通用理论的研究较少,对于应用性研究也过于局限。因此,有必要将研究的部分重心转移到通用性好、运算速度快且精度高的优良算法上来,以缩短存在的技术差距,健全快速发展的物流业,促进经济的进一步发展。
参考文献
[1]张强,荆刚,陈建岭.车辆路线问题研究现状及发展方向[J].交通科技,2004,(1):60-62.
[2]胡大伟,朱志强,胡勇.车辆路径问题的模拟退火算法[J].中国公路学报,2006,19,(4).
[3]唐小明,郭晓汾.基于物流配送服务水平多指标的车辆模糊优化调度[J].西安工业学院学报,2005,25,(3).
[4]骆义,谢新连.物流配送车辆调度优化研究[J].大连海事大学,2003,(3):7-12.
[5]宋华,胡左浩.现代物流与供应链管理[M].北京:经济管理出版社,2000,11,4.
物流配送车辆路径优化的仿真分析 篇3
1配送车辆路径优化问题的提出
具体而言,此问题的目的在于完成货物配送任务的过程中,以最少车辆数、最小车辆总行程去完成,这样就可实现时间最短或成本最小的目标,在路径的优化方面,有启发式算法、精确算法等多种类型,但都不够完善,存在各自的缺陷,难以获得最短路径的最优解,而最近几年出现的遗传算法等存在收敛速度慢、求解时间长的缺陷,这使得其往往只能找到近似最优解,存在一定的局限性,而本文研究的蚁群算法表现为一种群智能优化,在巢穴和食物间的最短路径的寻找方面,其借助正反馈并行机制和蚂蚁间协作来实现,优势较多,如求解速度快、具有并行性等,有着广泛的应用前景[1]。
2建立数学模型
具体实施中,走什么样的路线进行运输显然是物流配送车辆调度的实质,在已知客户需求量及车辆载重量的前提下, 为实现需求且车辆的总行程最短的目标至少需要派多少辆车,这就是最小成本的配送方案的由来,需对以下条件进行满足: 首先是以配送中心为起点,对应的配送车辆能最终回到配送中心; 其次,每辆车只能服务一条路线,同时每个客户只被一辆车访问一次; 再次,以车辆的载重量为基础,每条配送路径上客户需求量之和不能超过它; 最后,则是不能重复走每辆车的路线。基于上述要求,显然找到一条最优物流配送路线即为物流配送车辆路径优化的目标,从而实现最小配送费用。 V = { v0,v1,…vn} ,v0为配送中心,客户的所在地用vi表示,设K为配送中心可最多用的车辆数目,对应的Qi则为每辆车载重量,这样,我们就可借助建立的数学模型表现物流配送车辆路径最优化算法问题[2]:
上式中,k辆车所配送的顾客点数用nk表示,而顾客点在路径k中的顺序为i则用rik表示,最优解的限制条件如下:
2蚁群算法主要内容
近年仿生优化算法的发展速度较快,得到了很大的应用, 蚁群算法主要通过模仿来取得问题的解决,该算法的基本思想主要是对蚁群的觅食过程进行必要的模拟,所求问题主要是可行解集,在最优解的求解,是借助蚁群的正反馈和分布式协作机制来进行的,利于对二次分配及作业安排调度等方面的求解。
3配送车辆路径优化的蚁群算法设计
首先进行的步骤为确定蚁群数目,对应的我们设有n个客户数,m为蚁群中的蚂蚁数,则有:
式中,t时间位于客户i的蚂蚁的数目即为bi( t) 。
另外,主要规则是对蚂蚁路径转移规则的研究,本文所探讨的物流配送车辆路径问题中,其转移概率势必要对下一个客户点路径长度和路径上的信息素浓度进行考虑,物流配送中心可用O表示,j表示能够访问的客户点。这样,k到i向j选择转移的公式如下:
若j∈Q,否则( 4) 式中,tij表示i到j所有d时间,tij表示权重系数,β 表示期望启发式因子,α 表示信息启发式因子,ηij( t) 表示与路径( i,j) 相关联的启发式信息值:
再次,为信息素更新规则。为了充分利用循环最优解,需要对不同蚂蚁信息素进行循环,循环之后进行更新,如下公式:
其中,信息素挥发系数为 ρ,表示为[0,1]间的随机数,信息素残留因子用1 - ρ 表示,而本次循环过程中路径( i,j) 上的信息素增量则用 Δτij( t) 表示,对应的,本次循环中残留在路径( i,j) ,第k只蚂蚁的信息素总量用 Δτkij( t) 表示,继而出现:
其中,Q在式中作为常数,既信息素浓度,第k只蚂蚁在一次循环中的路径用Lk表示。
4车辆配送路径算法的实现
当前物流业发展中,对车辆配送路径优化问题的求解方面,借助于蚁群算法的方式,可借助人工蚂蚁替代车辆来服务客户点来实现,返回到配送中心的标准是下一个服务客户点会使运载总量比最大距离超过一次最远行驶距离或是汽车载重量更多的时候,不同车辆完成的此次运输,在此基础上,车辆可以对其他客户进行全方位服务,继而该车辆的人工蚂蚁就可以完成一次巡游标志,该标记是对客户进行的一次服务, 一次服务也可以是一次循环,之后,需要根据蚂蚁巡游路径的好坏程度将其他信息素进行分配,从而更好的对信息素增量进行不同程度的更新,以此进行不断的更新,得到最优路径或是选择相同路径,这样就可以完成求解了。
5结束语
综上所述,本文为达到对物流运输系统中车辆的路径的合理规划,本着对物流企业经济效益提高的目的,积极分析了物流配送车辆路径优化问题,后续研究中利用蚁群算法鲁棒性强等特点,在对此问题进行求解的方面提出一种基于蚁群算法,后续检验证实,本方法提高了寻优效率,对于最优解能快速找出,此方法具备了广阔的应用前景。
摘要：当前物流行业发展中,基于行业的发展需要,以及传统物流在降低物流运输成本方面无法克服的短板,急需进行物流配送车辆路径优化,从而有效地降低物流配送成本,基于此,文中提出一种蚁群算法的物流配送车辆路径优化算法,旨在建立数学模型的基础上,对物流车辆路径的问题采用蚁群算法进行求解优化,后续实验得出,该算法效果显著,利于对物流配送成本的降低,对于当前物流企业的发展意义重大。
车辆配送路线优化 篇4
1 绪论
1.1 研究内容
配送是物流活动中一种非单一的业务形式, 它与商流、物流、资金流紧密结合, 并且主要包括了商流活动、物流活动和资金流活动, 可以说它是包括了物流活动中大多数必要因素的一种业务形式。从物流来讲, 配送几乎包括了所有的物流功能要素, 是物流的一个缩影或在某小范围中物流全部活动的体现。一般的配送集装卸、包装、保管、运输于一身, 通过这一系列活动完成。由于经济发展带来了货物的急剧增加, 消费向小批量、多批次、多品种转化, 销售企业向大型化、综合化发展, 使得配送数量迅速增加, 同时超市商品种类的多样性, 也使得配送工作难度增加。
本文就区域超市配送系统的关键技术中的车辆调度问题进行了研究, 关键技术即是指集货、配货及车辆调度优化。其中, 重点研究了合理确定配送路线的问题, 这是整个配送网络优化的关键环节。合理确定配送路线就是用最少的动力, 走最短的里程, 花最少的费用, 经最少的环节, 以最快的速度把货物运至用户手中。
1.2 研究方法
在研究过程中, 通过选取苏果超市的部分配送区域, 就配送系统的优化问题用数学方法进行了定量分析和研究, 对各个配送点的需求进行假设, 建立了数学模型, 通过分析计算得出该配送区域的最优配送路线和车辆数量的需求数量。
1.3 研究目的
对物流配送系统进行分析, 得出优化方案, 节约物流成本, 从而提高企业的利润。同时通过研究, 进一步了解物流配送中车辆优化调度对节约企业成本的重要影响, 对提高劳动生产率、提高经济效益、实现物流科学化、促进社会发展和经济建设的重要作用。企业只有改进物流环节, 重视配送优化, 才能降低物流成本, 减少运营费用, 提高配送效率, 从而取得优势。
1.4 研究意义
合理规划配送路线对配送成本的影响要比一般运输大得多, 所以必须在全面计划的基础上, 制定高效的运输路线, 选择合理的运输方式和运输工具。选择合理的配送路线, 对企业和社会都具有很重要的意义。
2 案例分析
该方案拟在需求点附近设置一处配送中心, 对各需求点进行超市商品的配送。由于物流成本在企业中占很大比重, 而配送是企业物流中的关键环节, 所以需要对该区域的配送线路进行优化, 从而得到最短路径, 节约运输成本, 从而降低企业的运营成本, 提高利润。
3 优化方法
3.1 一般VSP模型
为构造数学模型, 将车场编号为0, 任务编号为1, …, l任务及车场均以点i (i=0, 1, …, l) 来表示。定义变量如下:
则可得到车辆优化调度数学模型如下:
模型中, cij表示从i点到j点的运输成本, 它的含义可以是距离、费用、变量、时间等, 一般根据实际情况确定, 可同时考虑车辆数和运行费用, 如下确定:
(1) 当i为车场时, 包括固定费用和运行费用
(2) 当i为任务时, 只有运行费用, 即
其中, c1为相对于运行时间的费用系数;c0为车辆的固定费用, 即增加一车辆的边际费用。一般认为, 派出一辆车的固定费用远远高于车辆的行驶费用, 因此该模型在极小化车辆数的前提下, 再极小化运行费用。减小c0的值将会是使用的车辆数增多, 而线路长度缩短。若令c1=0, c0>0, 则模型目标是使用的车辆数最少。
3.2 节约算法
节约算法是指用来解决运输车辆数目不确定的问题的最有名的启发式算法, 又称C-W算法, 是由Clarke和Wright于1964年首次提出的。核心思想是依次将运输问题中的两个回路合并为一个回路, 每次使合并后的总运输距离减小的幅度最大, 直到达到一辆车的装载限制时, 再进行下一辆车的优化。首先把各点单独与源点0 (车场) 相连, 构成1条仅含一个点的线路。总费用为两倍的从原点到各点的距离的费用。然后计算将点i和j连接在一条线路上费用的“节约值”:
S (i, j) 越大, 说明把i和i连接在一起时总路程减少越多。
4 优化方案
4.1 案例数据分析
各超市地理位置如图1:
各超市序号编排如下: (A为0, F为1, D为2, C为3, H为4, E为5, G为6, B为7)
各配送超市之间的最短距离及各门店对常用需求量如下:
从以上的配送线路可以看出, 原有配送线路实载率很低, 运距距离较大, 成本较高。物流配送过程中资源得不到充分利用, 造成一定程度的资源浪费。
4.2 模型建立与求解
利用节约里程法进行求解。
第一步:各配送点之间的最短路径及总的需求量。
第二步:求出各配送点之间的节约里程。
第三步:节约里程排序结果。
第四步:根据节约里程排序表和约束条件得到最优解
优化后的车辆调度结果为:
通过对前后配送路线的比较, 可以发现优化后的配送路线由之前的3条减少到2条。优化前需要派出3辆车, 总运距为74.4km。而优化后的路线只有2条, 只需要派出2辆车, 减少了1辆车, 总运距为56.7km, 减少了17.7km。按照派出一辆车的费用为150元来算, 可以节约150元。运费减少了25.56。优化后的路线成本可以节约175.56元。并且派出的车辆得到了比较充分的利用, 平均装载率达到了91.54%, 比原来的线路增加了12.21%。
5 总结
本文以苏果配送中心配送方案优化设计为背景, 选取南京七家苏果超市进行配送路线研究, 结合零售业的实际情况, 各个门店对于某些常用商品的需求是稳定而不间断的, 在研究这类问题的时候, 不需要讨论各个门店在不同时期对于不同货物的需求, 只要每次配送固定的商品即可, 对于这类问题采用启发式算法当中的节约里程法求出最优的配送路线设计的方案。
对于这类连锁零售企业, 配送成本最低和满足客户对时间的高要求是配送中急需解决的问题, 这都需要研究物流配送路径优化模型和算法来解决这类问题。从配送中心到客户位置的物流在配送领域是一个负载的调度问题。如果能通过比较科学的物流配送路径优化模型和算法, 来实现企业的人工调度和车辆安排, 使得物流中心本身运作效率更高, 成本控制得当, 企业的效益也会不断提升。
摘要：物流业的发展对经济活动的促进作用越来越大。配送是物流中一个重要的环节, 并且与消费者相关联, 配送路线优化, 是物流配送中关键的一环, 对企业节约成本、增加利润起着重要的作用。文中对区域超市配送问题进行了研究, 以苏果超市为例, 利用节约算法, 考虑了约束条件, 并建立了数学模型, 运用算法得出该企业最佳配送路线和车辆的综合调度方案。
关键词：配送路线优化,节约算法,数学模型
参考文献
[1]高晓亮, 伊俊敏, 甘卫华.仓储与配送管理[M].北京:清华大学出版社, 2006.
[2]孔少彻, 梁彤铮.商品物流配送优化策略探讨[J].市场论坛, 2009, (7) :94-95.
[3]蔡临宁.物流系统规划—建模实例分析[M].北京:机械工业出版社, 2003.
[4]孙焰.现代物流管理技术[M].上海:同济大学出版社, 2004.
[5]王鑫.物流配送中车辆优化调度问题的研究与实践[D].沈阳:沈阳航空工业学院计算机应用技术, 2006.
[6]徐剑, 牟燕妮等.物流配送车辆调度优化方法比较研究[J].物流科技, 2006, (2) :46-49.
[7]许星, 物流配送路径优化问题的研究[D].浙江:浙江大学计算机科学与技术学院计算机应用技术, 2006.
[8]韩世莲, 物流配送线路多目标优化方法研究[D].江苏:东南大学载运工具运用工程, 2006.
[9]李金苹.现代物流配送系统的运输优化调度方案[J].物流技术, 2002, (5) :11-13.
车辆配送路线优化 篇5
1 成品油配送中车辆优化调度的过程分析
在成品油的储运过程中, 最核心最关键之处就是要加强物流配送车辆的优化调度, 要确保物流运输的合理化, 这是控制成本、增强企业竞争力的关键。配送体系是由多个配送中心组成的有机体。物流配送中心车辆调动的过程, 其实就是立足于总体的配送目标, 采用系统原理, 选择交通路线和交通工具, 组织交通运输活动, 争取做到最快速度、最短路径、最少消化以及最少环节。成品油配送中车辆的优化调度其实就是通过对路径、交通路线以及交通运输工具等各个方面的选择来优化调度方案的过程。
2 车辆调度优化的基本方法
在车辆调度优化系统中的调度优化问题较为复杂, 为了降低求解难度, 一般来说, 我们会将技术难题加以分解和转化, 将其转化成为已经研究过的基本问题, 进而加以求解。基本问题包括但是不限于以下问题:分派问题、背包问题、旅行商问题、最短路问题、运输问题以及中国邮路问题等等。常用的方法主要是线性规划法、匹配理论、组合理论、统计分析、经验分析、动态规划法、割平面法等等。
3 物流配送车辆优化目标及调度模型
成品油的汽运过程中, 不同的货运任务, 需要的车辆数量是不同的, 再加上每个货运任务都有其集货点和送货点, 这就需要我们结合具体的情况来确定车辆行驶路线进行车辆优化调度。
首先, 按照货主的要求送货以提高物流服务质量, 这也是我们优化的中心目标之一。其次, 从节约成本和提高经济效益的角度规划物流配送的相关要素, 即追求配送时间准确性的前提下尽可能地追求成本最低化;最后, 追求空载率最低化, 即追求配送车辆的最大载重利用率。
我们会将车辆调动问题整合成各种存在一定关系的模型或者凸轮, 一般来说, 模型主要分为三种:以物流为基础的模型、以车流为基础的模型以及集覆盖模型。
4 车辆优化调度问题的分类研究
4.1 非满载车辆优化调度
当货主要求的成品油数量比运输车辆的容量小时, 车辆在运输过程中是以非满载的状态运行, 此时可以考虑让一辆运输车执行多项任务, 也就是说让不同货主的成品油装载于同一辆运输车进行运输。这里主要包括以下两种情况:
4.1.1 集货或送货单独进行
物流的运输是全部由集货点 (装货点) 或送货点 (卸货点) 车辆空车从车场 (泛指车辆出发地, 可以是车库、货场、仓库、配送中心等) 出发, 去各货主处装满货后返回车场, 或是车辆装满货物去各货主处卸货后返回车场。此时, 成品油运输总量低于一辆运输车的装载量, 完全可以由一辆车来执行多项任务, 称为有容量限制的TPS问题。
4.1.2 集货和送货一体化
集货和送货一体化是指成品油的每一次运输都存在着其集货点和送货点, 车辆一般先统计到集货点进行装货, 进而统一到送货点卸货, 在运输任务完成之后, 车辆要再次回到原先出发的车场。如果集货点和送货点较为分散, 并且货运任务容量较大的情况, 容易造成车辆空驶, 货物难以混装;相反情况, 可以安排一辆车在几个集中点装卸。
4.2 满载车辆优化调度
当货主要求的成品油数量较大, 超过运输车辆的容量时, 进行成品油配送的车辆可能远不止一辆, 为保证货主货物量, 车辆一般为满载运行。满载成品油的货车, 从车场出发到几个集货点装卸后返回车场 (仅有装货) , 或是车辆出发到几个送货点卸货 (仅有卸货) 后返回车场。此时的车辆优化调度按照车场的不同, 可分为单个车场的优化调度与多个车场的优化调度。运输车辆来自同一个车场时, 由于每项任务的货物量较大, 每辆车只能去执行一项任务, 这时, 车辆直接从车场到任务点装货 (或卸货) 后返回车场。运输车辆直接按照出发地与运输地的最短路线运输即可, 不需要对运输线路进行优化。运输车辆来自不同的车场时, 即从多个车场出发的车辆到多个任务点执行运输任务, 这种情况即为运筹学中的一般的运输问题, 一般用表上作业法解决运输问题。首先确定初始基可行解, 按单位运价的大小决定供应的先后, 优先满足单位运价最小者的供销要求, 即从单价中最小运价确定供应量, 逐步次小, 直至得到m+n-1个数字格;其次, 进行解的最优性检验, 通常采用闭回路法计算空格 (非基变量) 的检验数;最后, 进行解的调整, 即从检验数为负值的格出发, 做一条除该空格外其余顶点均为有数字格组成的闭回路, 在这条闭回路上对空格的运量作最大可能的调整。需要指出的是, 运输过程中是以卡车为单位, 车辆不装满的话就不能实现效益最优化, 而整数解性质可以避免运输方案为小数的麻烦。
参考文献
[1]孟小平.物流配送及其运输调度优化研究[D].大连海事大学2001.
[2]宋洁蔚, 荣冈.成品油配送中时间窗的确定及运输的安排[J].系统工程理论与实践.2003 (04) .
车辆配送路线优化 篇6
目前，具有小批量、多批次特点的实时的城市配送的不断发展大大增加了配送成本，不合理的配送方案会严重增加城市交通负担。与城际配送等长距离的配送相比，城市配送货物需求点繁多且分布不均匀、单批需求量小且时常发生变动、道路堵塞情况时有发生，初始规划路线往往不能保证最小化企业运输成本，而且顾客可以通过移动电子商务平台随时随地进行订单的添加、取消和订货量的变更，加大了对配送实时响应性和灵活性的要求，增加了配送路径安排的难度。
实时的城市配送需要借助地理信息系统（GIS）、全球定位系统（GPS）、智能交通系统（ITS）、移动电子商务平台（MC）和全球移动通讯系统（GSM）等技术工具实时地获取动态信息，而调度中心要不断的合并新信息，在每个动态事件发生时刻生成新的配送计划。信息获取过程如下：MC用于获取顾客需求量和需求点位置信息，ITS用于获取实时交通道路信息，车辆使用GPS进行定位，GIS用于获取任意两个顾客的实际距离。根据以上实时信息，每次有动态事件发生，配送中心生成新的配送路径方案，其指令通过GSM传达给车辆司机。
关于动态车辆路径问题的研究在近10年取得了一定的进展。谢秉磊和郭耀煌[1]对动态车辆路径问题的研究进行了综述，并对该问题的发展前景进行了展望。针对在配送过程中有事先未知位置的新顾客出现的情形，Branke[2]提出了以最大概率将新顾客整合到原配送方案的等待策略。Potvin[3]针对考虑顾客实时需求和动态行驶时间的动态车辆路径问题，比较了不同的调度策略。针对动态网络环境下的车辆路径问题，王江晴[4]提出了一种实时路径评估模型，用于找出实时最短路径，在此基础之上构造了一个改进的Dijkstra算法，实现对行驶线路的不断调整。Du等[5]以牛奶配送为应用背景，提出车辆实时调度中采用2-Exchange改进法则用于配送线路内部的改进十分迅速有效。刘霞[6]研究了带时间窗的动态车辆路径问题，使用插入法构造初始解，使用重定位法、节点交换法、2-opt法和Or-opt法4种局部搜索方法的不同组合完成对初始解的改进。刘士新[7]设计了在动态环境下的车辆路径问题，提出一种导向局部搜索算法，算法对初始解中各车辆配送路线的顾客服务顺序进行动态改进。针对具有模糊预约时间的动态车辆路径问题，张建勇[8]提出了在新顾客出现时的一种插入启发式算法，确保顾客综合满意度最大。针对出现新需求的情况，Attanasio等[9,10]提出了接受或拒绝新订单的策略。郎茂祥[11]考虑车辆故障和允许多次配送的情况，提出了包括制定整体计划和实时局部优化的两阶段策略，分别采用禁忌搜索算法和局部搜索算法进行求解。针对配送车辆在配送途中出现故障的情形，Li[12]提出了一种拉格朗日松弛插入算法安排其他配送车辆完成故障车辆尚未完成的配送任务。王旭坪[13]等从干扰管理的角度，提出了解决配送过程中出现动态信息的方法。陈森[14]针对路网结构变动和需求随机双重不确定因素的动态车辆路径问题，设计了加速自适应遗传算法进行求解。针对带时间窗动态车辆路径问题，王君[15]通过定义紧急顾客，提出基于紧急顾客插入的重复优化方法、分批处理的方法或上述两种方法的的混合三种应对策略。
对于动态车辆路径问题，目前相关研究多采用插入新需求点和调整部分线路的局部优化方法，尽量减少原有配送线路的变动程度。针对可能发生的动态事件，通常只选取其中的一种或两种情形作为考虑对象。
针对现行研究存在的上述问题，本文考虑配送过程中可能发生的多种动态事件，在每次动态信息更新后在原有配送方案基础上对剩余尚未配送的顾客需求点进行全局优化。提出了一种能够即时处理各种动态信息的车辆实时调度方法，考虑了顾客接收货物的时间窗限制和车辆超出最大距离的附加成本。通过实时收集顾客需求信息、监测车辆运行情况，对已经安排好的车辆路径进行即时调整或重新安排车辆所需服务的顾客需求点，实现配送路径的实时优化调整。
2 实时车辆调度问题描述与模型构建
2.1 建模假设与符号说明
本文研究的动态车辆路径问题，可定义如下：在保证每个顾客的需求被满足，且不超过配送车辆的最大配送量，考虑车辆超出最大行驶距离和违反时间窗限制的附加成本的情况下，考虑配送过程中实时变化的信息（需求点增减、需求量变化、道路交通中断、配送车辆故障），每当有动态事件发生时应该如何重新安排车辆的行驶路线，目标是使整个配送周期的车辆配送总成本最小。
本文假设配送中心有一定数量的配送车辆，车辆载重量均为Q，所有顾客的货物需求量均小于配送车辆的最大装载能力，车辆由配送中心出发，完成配送任务后要返回配送中心，方案计划安排的车辆数为m，平均车速为v.c为单位距离运输成本，c0为多派出一辆车的固定成本。车辆每日最大行驶距离为L，超出最大行驶距离后的惩罚系数（即每公里需附加支付给司机的费用）为pl，违反时间窗约束的惩罚系数为p1、p2.
每当有动态事件发生时，更新所有相关信息，包括：已经完成服务的顾客集合I1={1,2，…，n′}；尚未服务的顾客集合I2={1,2，…，n}，顾客i的货物需求量qi、服务时间si及顾客位置，i∈I2，顾客i要求货物最好在时间窗[ETi,LTi]内送达，最差不得超出[ai,bi]的送货时间范围；尚未服务和已服务的所有顾客集合I={1,2，…，n′，…，n′+n}；正在执行任务车辆集合H={1,2，…，h}，各车的位置和状态（车辆是否发生故障），各车在该时刻已完成的货物配送量Qk和已行驶的距离Lk,k∈H；当前所有节点集合（尚未服务的顾客、虚拟顾客、配送中心）N={0,1，…，n，…，n+h}，任意两节点距离dij，及现有节点间各路段交通状况（道路交通中断时dij取无限大），i,j∈N；尚未服务的顾客和虚拟顾客的集合D={1，…，n，…，n+h}。
动态事件发生时，对尚未服务的顾客重新编号1,2，…，n，虚拟顾客编号n+1,n+2，…，n+h，配送中心编号仍为0，将正在执行任务的车辆（亦即该路径）与各自虚拟顾客n+1,n+2，…，n+h对应编号为1,2，…，h，从配送中心出发的车辆顺次编号为h+1,h+2，…，m．配送车辆集合M={1,2，…，h，…，m}。
决策变量xijk表示车辆k经过路径（i,j），有
车辆k到达顾客i的时间为TAi，离开时间为TLi．显然有，，递推可得，而TLi=TAi+si.
2.2 问题分析与转化
根据配送开始之前的已知信息，按照静态车辆路径问题的方法进行求解，所得即为初始配送方案。
配送开始之后有任何一种动态事件发生时，部分车辆正在配送途中进行配送。此时，需更新所有相关信息进行重新调度。该时刻点的路径安排问题可视为多车型的混合式车辆路径问题，原因如下：
(1)在配送中心尚未出发车辆的货物配送量是Q吨，其最大行驶距离为L；在配送途中的车辆已经完成Qk吨货物配送量，车上剩余Q-Qk吨货物配送量，其最大行驶距离为L-Lk．因此，在配送中心尚未出发的车辆和在配送途中的车辆可以看作不同的车型。
(2)在配送中心即将出发的车辆最终会回到配送中心，其行驶路线是闭合回路；在配送途中的车辆此时不在配送中心，相当于从该时刻点该车辆所在途中位置出发，最终返回配送中心，其行驶路线是开放式的路径，而不是闭合回路。因此，在重新调度时，可以将该问题看作是包含封闭式和开放式车辆路径问题的混合式车辆路径问题。
进一步将多车型的混合式车辆路径问题转化为静态单车型车辆路径问题，转化方法如下：
(1)将在配送途中正在进行配送的车辆k当前所在的位置设置一个虚拟顾客，其需求量为Qk，该虚拟顾客与配送中心的距离为Lk.
(2)在配送途中正在进行配送的车辆必须首先服务其对应的虚拟顾客。
2.3 数学模型
根据上述求解思路，本文提出的动态车辆路径问题模型建立如下。
目标函数：
其中，
约束条件：
模型中，式（1）表示问题的目标函数配送总成本最小，包括车辆的运输成本、车辆启用的固定成本、超出最大行驶距离附加成本（2）和违反时间窗限制的惩罚成本（3）；约束（4）保证每辆配送车辆均不超过其最大载量能力；约束（5）、约束（6）确保每个顾客只能被分配到一条路径上，即只被服务一次；约束（7）保证每一条路径上，离开每个节点的车辆数等于进入该节点的车辆数；约束（8）确保所有车辆的起、终点都在配送中心；约束（9）表示每辆当前正在执行任务的车辆必须首先服务其对应的虚拟顾客，从而使配送的路径转化为简单圈；约束（10）限制车辆行驶路径轨为简单圈，避免子回路的产生。式（11）为到达时间的非负性约束。
3 混合遗传算法设计
3.1 实时调度的整体流程
步骤1：数据初始化。开始时间为0，全部车辆起始位置在配送中心。根据现有的相关信息，利用混合遗传算法生成初始配送方案。
步骤2：车辆司机严格按照调度中心传达的配送线路行驶。
步骤3：判断是否已经完成所有配送任务或达到最长工作时间。若是，结束任务，车辆返回配送中心；否则，转步骤4。
步骤4：发生动态事件时，更新相关信息，得到一组新的需求节点和需求量，在途车辆状态、位置的集合，以及当前各路段交通状况的相关信息。
步骤5：调度中心根据最新雅息对配送车辆的行车路线进行重新安排，并将新的行车路线即时传达给配送车辆司机，下转步骤2。
3.2 混合遗传算法步骤
根据模型的结构特点以及决策变量的可行域，本文设计了结合局部搜索思想的混合遗传算法，在每次信息更新后重新对配送路线进行求解，从而实现实时调度。混合遗传算法按以下步骤进行：
Step1：编码，生成初始种群。采用需求点直接排列的编码方法，用一个染色体表示所有尚未服务的需求点的配送顺序，即由尚未服务的顾客编号1～n构成一个实数串。随机产生未被访问过的需求点序列，按顺序逐一将每个需求点加入到当前配送路线中。检验是否满足车辆载重限制，若满足，则将该需求点加入到当前配送路线中；若不满足，则将其加入到下一条配送路线，如图1所示。
重复上述过程得到N条染色体。
Step2：计算个体适应度。P=1/（Z+Gpw）。式中Z为目标函数值，G为配送路径条数与配送中心的车辆总台数之差（若配送路径条数<车辆总台数，则取G=0，表示该个体对应一个可行解；否则，G>0，表示该个体对应一个不可行解），可将G看成该个体对应的配送路径方案的不可行路径条数，设对每条不可行路径的惩罚权重为pw．若适应度值满足优化准则，满足转step8，否则转step4。
Step3：选择再生个体。采用轮盘赌选择具有较高适应度的个体。保留当前子代的最优解，并保持子代的群体个数与种群个体数相同。
Step4：交叉方法采用类改进的OX法实施交叉操作。操作方法说明如下：选择两条父代染色体，随机选择两个基因交叉点，在两个父代个体前分别加入异方双亲的交叉区域，顺次删除与交叉区域重复的基因，得到子代染色体。交叉操作示意图如图2。
Step5：变异。对子代进行两点交换操作。交换前后进行适应度计算，如果其适应度比之前好，那么采用变异后的值，如果较差，则再进行一次随机变异。
Step6：判断是否达到预先设定终止进化代数，满足转下一步，否则返回Step2。
Step7：输出最优解，算法停止。
4 算例设计与结果分析
4.1 算例设计
某城市配送中心位置坐标为（112,88）。共有15台配送车辆，拥有若干个位置已知的潜在需求点。运输成本c=1元/公里，多派出一辆车的固定成本c0=100元，车辆最大货物配送量Q=8吨，车辆每日最大行驶距离L=250公里，超出最大行驶距离后每公里需附加支付给司机的费用pl=1元/公里，p0=20元，p1=p2=50元/小时，ai=ETi-2,bi=LTi+2,A=10000元，平均车速v=50公里/时，粗略将需求量（吨）的1/3记为该需求点的服务时间（小时）。
在配送开始前有8个货物配送任务，各个顾客的需求情况如表1所示。
4.2 对比策略
将本文所提出的实时调度方法与传统的静态调度方法进行对比实验。
传统的静态调度方法是指所有配送车辆均按照配送开始前的初始配送方案进行配送，配送顺序和配送量均不作任何变动。对于配送过程中可能出现的各种动态情形，采取如下方式进行处理：
(1)在配送过程中，对于新增需求点和需求量，从配送中心另外派出车辆进行配送，调度方法与静态车辆路径问题相同。
(2)对于取消订单的需求点，配送车辆直接将其略过，对下一顾客进行配送。
(3)对于在途中发生故障的车辆，从配送中心另外派出车辆按照顾客点顺序依次完成该车未完成的配送任务。
(4)对于两需求点间发生交通中断的情形，该配送车辆直接对原路线的下一需求点进行配送，发生交通中断而无法到达的需求点由新派出的车辆进行配送，调度方法与静态车辆路径问题相同。
4.3 结果分析
(1）初始配送线路的构建
使用混合遗传算法进行求解，得到初始配送线路。配送中心需派出3辆车，配送路线分别为：0-1-4-5-0,0-8-22-0,0-17-16-15-0。
(2）实时信息下的线路优化
(1)情形1:
T1=1时20分，发生如下动态事件：老顾客4、22分别新增需求0.5吨，老顾客5取消订单，出现新顾客6、7、10、11、19、28、29。此时，尚未服务的顾客需求见下表。
对信息变更后的配送任务运用混合遗传算法重新构造配送路线，得到的配送方案如表3。
若使用传统的静态调度方法，可以得到如下配送方案。
对比表3和表4可以得出，如本算例在需求点和需求量发生变动的情况下，采用本文所提出的动态车辆调度方法可以降低总配送成本，在该算例中可以有效降低157.8元，高达原配送成本的10.4%.
(2)情形2:
T2=2时，发生如下动态事件：车辆2在行驶途中发生故障，短时间内无法修好；顾客15、16之间的交通中断。此时，还剩下顾客4、5、15、22未被服务。
对信息变更后的配送任务运用混合遗传算法重新构造配送路线，得到的配送方案如表5。
若使用传统的静态调度方法，可以得到如下配送方案。
对比表5和表6可以得出，如本算例在车辆发生故障和部分顾客间出现交通中断的情况下，采用本文所提出的动态车辆调度方法可以降低总配送成本130.7元，降低14.6%，显示了本文动态车辆调度方法的有效性。
5 结论
对于需要具备快速响应能力的城市配送问题，本文通过引入虚拟顾客的概念，将实时信息下的动态车辆路径问题转化为经典的静态车辆路径问题。借助GIS、GPS、ITS等技术工具获取实时信息，解决了四种动态事件情形下的配送线路实时优化调度。运用所提出的混合遗传算法求解模型，通过算例测试，与传统的非实时配送方案进行对比，得出该调度方法可以有效地找到实时最短路径、降低配送成本。
车辆配送路线优化 篇7
对于地下物流系统，国外的学者多集中于对这一系统的可行性研究以及地下物流系统的建设，在德国、日本、荷兰等国家，早已有建成的地下物流线路投入使用。
在国内，从2002年杨涛等[1]发表的《新型城市地下货运交通系统》开始，陆续有越来越多的学者开始关注这一研究方向，主要包括马保松等[2]对地下物流发现现状及历史的介绍，钱七虎院士对用地下物流系统解决特大城市交通拥堵问题这一思路的肯定，以及杨文浩[3]对现存问题的思考和策略。
目前，大多数研究主要探讨的是地下物流系统的可行性，风险评价和整体网络的规划问题。如HenryLiu[4]的《Feasibility of underground freight transport in New York City and lessons learned and implications to other major cities in the world》，介绍了纽约城市管道货物运输的概况,讨论了它对其他城市的启示，为相关领域的交通规划者提供了必要信息。傅方方[5]的《城市地下物流系统风险评价及发展前景研究》则采用层次分析法和综合评分法建立综合评价模型，对地下物流系统面临的投资风险进行评价。而李彤[6]认为，可以采用模拟植物生长算法来进行大型城市地下物流网络的优化布局。
而针对地下物流系统配送线路等问题目前的研究并不多，综合各类文献不难发现，地下物流运输与一般公路运输的区别之一就在于地下物流运输隧道的建设成本远远高于公路建设的成本，所以线路建设成本必须纳入考虑。而在进行物流配送活动时，时间问题正渐渐成为人们非常关注的问题。基于此，本文从整个系统的成本的角度出发，选择了投资成本和时间成本最小为目标函数建立了地下物流配送路线优化模型。
1 考虑时间成本的ULS路线优化模型的建立
1.1 问题分析
在进行地下物流配送路线设计时，可以结合已有的公路运输路径优化的一些方法。但是地下物流系统配送路线的设计还有许多特殊之处。
首先，地下物流系统的大部分工作场所都处于地下，包括运输线路。不同于公路运输的道路网络化，地下物流系统尚未发展成熟，所选路径必须专门进行规划、设计和建设。所以，在进行线路设计工作时，必需考虑因隧道建设等工作所带来的费用问题。
第二，地下物流系统的建设面临着的挑战之一就是巨额的投资。如果仅仅依据ULS所得的直接经济效益和直接费用来进行评价这一新兴运输系统，很显然，与公路运输相比，ULS并不占优势[7][8]。因此，在进行路径设计及优化时，若盲目参照已有的路面运输路径优化方案，一味地考虑运输成本问题则很不合理。
第三，地下物流系统在一定程度上比路面运输要自由，它可以实现直线运输，大大缩短了运输时间[9]。同时，与地面运输相比，“拥堵”这类情况将大大减少。所以，在进行路线选择时，几乎不用考虑因交通事故、道路损毁等引起的交通拥堵造成的时间损失。
在地下物流运输网络中，线路建设费用、运输费用、运输时间、运输质量及运输服务水平都是影响地下物流配送路线选择的重要因素[10]。其中，运输质量和运输服务水平的衡量指标虽然包括设施条件、场站服务质量等要点，但更大程度上来自于货物的配送时间即准点率。由于地下物流系统运行环境和条件的特殊性，在进行配送活动时，货物到达的准点率更易控制，这为配送工作带来便捷的同时，也要求配送线路要更加合理可行。
综合上述原因，本文以路网总成本最小为目标函数建立模型进行讨论。
1.2 模型假设
鉴于地下物流网络建设的投资成本偏高，地下物流系统更适用于发展较快且货流量偏大的城市[11]。为使模型更加合理可行，现对模型作如下假设：
(1)为了研究方便，本文讨论的运输货物不分品种；
(2)参与地下物流运输过程的车辆型号相同、容量相同，车况也相同，本文假设使用的是自动导向车。
(3)物流线路中每个节点的物流需求数量和位置已知；
(4)每个客户都必须接受配送服务；
(5)配送中心的货物量可以满足总的客户需求量；
(6)物流配送车行驶过程中速度固定不变。
1.3 模型构建
假设在一个地下物流系统中，现需在N条备选线路中选出合理的地下物流轨道线路，使得这个地下物流系统可以完成配送任务。因为本文针对的是货流量偏大的城市，为了简化问题，将配送中心和需求节点无差别化，都视作一般节点，一共有M个节点。由于本文在建立模型时，已经单独考虑了货物在各站的停留时间，所以可以不必再考虑货物经线网到达目的地过程中的“换乘时间”。
设地下物流轨道线路k的长度为lk；每公里的建设费用为ck；每公里的运营费用为dk；配送车在行驶过程中速度固定不变，设为v；货物从节点i出发，到达节点j，中间经过h站，每站停留的时间记作tijp，起点处i的停留时间记作tijo，从i到j的线路长度记作Lij；以i为起点，j为终点的路段的货物运输量为xij;C为建设投资成本；T为时间成本；Z为总成本；a为时间成本权重。引入ηk，，其中，
那么，模型的数学形式表示如下：
约束条件如下：
上述各式，式（1）是地下物流运输线路双向约束条件，其中，i,j是物流节点，T为所有节点的集合；式（2）中，Lmin和Lmax分别为地下物流运输线路总的布设长度最小值与最大值，该式保证了线路规模的合理；式（3）保证了任意两个物流枢纽之间的可达性，sij则是任意两个物流枢纽i和j之间的最短路；式（4）和式（5）表示的是取值范围。
2 算法设计
遗传算法[12][13]具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。采用0-1编码的遗传算法可以解决本文的问题。具体步骤如下：
Step 1.编码：因为有N条备选路线，对其编号依次为：1,2，…，n，故染色体长度为n，因含有0-1变量，编码为:{1,0,0,…，1,0}，其中，0表示该位置的备选线路未被选中，1则表示线路被选中。
Step 2.适应度计算：对种群中每一染色体解码求得对应的可行解，根据公式（3）求得目标函数值Z，适应度计算公式如下：
Step 3.算子选择：将每个种群的P个染色体按适应度值依次排序，并将值最大的染色体复制进入下一代。对剩下的染色体采用基于排名的轮盘式选择策略，以选择进入下一代种群的算子。
Step 4.算子交叉：使用单点交叉法进行算子交叉，例如：
Step 5.算子变异：根据变异概率Pm，执行变异操作，令gen=gen+1，从而得到新种群，并转至步骤2。
3 算例验证
某发展规模较大的城市拟规划建设地下物流系统。经考察分析，要以地下物流线路连接7个主要物流区域。图中，线段上数值表示地下物流系统行车距离。设搬运车在路段上的走行速度为固定值,不考虑进出站加减速的情况下按20km/h取值[14]。为简化计算，设所有路段的建设成本均为45万元/m，营运成本为1万元/m，且所有站点的停留时间均设为0.25小时。时间成本权重取12元/h。假设仅考虑物流系统行车时间及每站停留时间。由于货物流量分布基本对称，所以，线路断面货物流量两个方向相等，因此，这里只考虑单方向的线路规划。
已知各边长度情况如表1所示。
假设有5条备选轨道线路，依次为：
规定规划地下物流线路总长度不宜超过40km，各物流区域间货物流通分布见表2。
采用本文所提出的模型和求解方法，采用0-1编码，因备选轨道线路条数为5，故染色体长度设定为5，种群数取200，交叉率取0.65，变异率取0.05，通过MATLAB编程，运行后得到最优地下物流线路如下：
4 结论
与传统的物流配送路径优化模型相比，本文所建的考虑时间成本的地下物流配送路线优化模型以总的运输成本最小为优化目标，并考虑可达性约束与线网合理规模约束条件，建立了地下物流系统网络布局优化的优化模型。不仅考虑了线路的建设成本和运营管理成本，而且考虑了每站停留时间和运行时间对运输成本的影响，这一点对于如今要求有更多可靠性、更快吞吐量时间、更高服务水平和更大灵活性的物流行业尤为重要。同时，运用所建模型可对可能的地下物流线路进行筛选，以得到合理的线路网络布设方案。所建模型为地下物流线路的规划提供了理论依据。
摘要：为了缓解目前紧张的交通拥堵形势,有效规划合理的地下物流网络,文中进行了地下物流系统配送路线优化研究。文中分析了目前地下物流系统的研究概况,指出了配送线路设计的特殊之处,提出了配送时间和线路建设成本对地下物流配送线路的影响问题,考虑配送线网合理规模约束与可达性约束,以地下物流配送线路的总成本最小为目标,建立了基于投资成本和时间成本的地下物流配送路线优化模型。采用遗传算法对模型进行求解,算例结果表明,运用该模型可对所有可能的配送线路进行筛选,并得到最优的线路网络布设方案。该模型可用于城市地下物流系统的规划中,对配送线路网络进行优化布局。