配送路线优化范文

配送路线优化范文（精选9篇）

配送路线优化 第1篇

一、配送路线车辆优化调度模型分析

1. 一般VSP模型

为构造数学模型方便,将车场编号为0,任务编号为1,,l,任务及车场均以点i(i=0,1,,l)来表示。定义变量如下:

则可得到车辆优化调度数学模型如下:

模型中,cij表示为从点i到点j的运输成本,它的含义可以是距离、费用、时间等,一般根据实际情况确定,可同时考虑车辆数和运行费用,如下确定:

(1)当i为车场时,包括固定费用和运行费用

(2)当i为任务点时,只有运行费用,即

其中,c1为相对于运行时间的费用系数;c0为车辆的固定费,即增加一辆车的边际费用。一般认为,派出一辆车的固定费远远高于车辆行驶费用,因此该模型是在极小化车辆数的前提,再极小化运行费用。减小c0的值将会使使用的车辆数增多,线路长度缩短。若令c1=0,c0>0,则模型目标是使用的车辆数少。

2. 时间窗VSP模型

设完成任务i需要的时间(装货或卸货)表示为Ti,又设任务i的开始时间需在一定的时间范围[ETi,LTi]内,其中ETi为任务i的允许最早开始时间,LTi为任务i的允许最迟开始时间。如果车辆到达i的时间早于ETi,则车辆需在i处等待,如果车辆到达时间晚于Lti,任务i要延迟进行。求满足货运要求的费用最少的车辆行驶线路。此问题称之为有时间窗的车辆优化调度问题。

以si表示车辆到达点i的时间,tij表示车辆由点i行驶到点j的时间,一般应有以下关系式:

二、应用举例

以北京通远公司配送中心为例,应用编制的配送路线优化调系统对现有的各个配送点进行优化。上海大众在北京的销售分中心的配送点现有34个,但其中有一部分不在北京市区,为于研究,特选取北京市区的部分配送点作为研究对象,各配送名称及位置如表1所示,各配送点之间的距离如表2所示,各送点的货物运输任务及要求如表3所示。

经过配送路线优化软件优化后,得到结果如下所示。

三、优化结果分析

经过配送路线优化调度系统优化后的配送与以前的传统配送相比,主要有以下优点:

1. 经过综合考虑路线的复杂程度后,可以提高配送的及时性,提高顾客满意度。

2. 多家集中配送的方式可以降低配送成本,为企业赢得更多利润。

3. 可以根据路线的实际交通情况,及时调整配送路线,提高配送的机动灵活性。

4. 能最大程度地满足客户的需求。

摘要：本文根据节约里程法的配送路线优化方法和思想,建立有时间窗的车辆优化调度模型,对集货或送货的非满载车辆优化调度问题进行研究,并编制了配送路线优化调度系统,选取北京通远外经国际运输有限公司的部分物流配送点进行了路线优化。

关键词：配送路线车辆优化调度,时间窗,物流配送

参考文献

[1]李化:北京通远企业配送供应链设计与线路优化研究[D].东北大学硕士论文,2007.8

[2]翁心刚:物流管理基础[M].北京:中国物资出版社,2006.6

[3]黄中鼎:现代物流管理[M].上海:复旦大学出版社,2006.2

[4]张念:仓储与配送管理[M].大连:东北财经大学出版社,2004.3

物流配送网络优化方案 第2篇

一、物流网点制定

1、考虑因素有：数量各点的规模位置主要职能进行市内配送，实现高频次周转该点仓租相对便宜，减轻的仓租费用的负担

2、方案的设计(1)在现有的销售网点中，选若干销售量大的点作为该区的物流网点。(2)覆盖区域的确定：以该点为中心，满足经济区域配送的范围为该区的区域。

优化物流配送线路降低物流配送成本 第3篇

当前配送线路的基本情况

伴随社会进步、烟草行业的持续性发展，卷烟营销面临着前所未有机遇和挑战：烟草营销网络的形成、发展和壮大，越来越多的客户成为烟草公司卷烟营销的对象，原有的卷烟营销思路和方法也逐渐与烟草现有的营销现状产生矛盾。按照营销的4C理论，对于买方成本的控制是提升公司营销能力和盈利水平的重要手段。复杂的地貌和相对分散的卷烟零售客户分布，使公司卷烟配送工作不得不面临的客观限制条件。

随着公司的发展，和卷烟销售网络的进一步发展、辖区内卷烟零售客户数量的增加，部分线路出现了运力吃紧的情况。随着时间的推移，与之相关的卷烟销售方面的问题一个个浮出水面，摆在了公司卷烟营销管理部的面前。

分析问题：

从反映的情况来看，公司卷烟营销面对的问题有以下几点：客户在不同访销日的分配不够合理；配送线路不合理，部分线路过长，部分车辆在部分时段配送工作量太大；销售计划受卷烟配送量的限制，不利于均衡销售；不同拜访日的客户因为销售计划的变化，得到卷烟数量不合理，产生了部分客户对于公司销售不满的现象。

从表面上来看，造成这些问题的原因，有两方面：一是上文提到的复杂的地貌和相对分散的卷烟零售客户分布；二是公司发展的零售客户数量的增加（由1100多户发展到1300多户）和公司营销网络在辖区中的扩展和向山区的延伸。

但是公司现有18辆送货车，按照每辆100万支的额定装载量，每天的送货量在600万支左右。问题的症结不在现有的卷烟配送能力上，而公司在物流流程和资源应用上存在亟待解决的问题：

以往，送货都是县、自然村为单位，进行线路的划分。按线路进行访销。由于各地方的经济发展速度不同，新增的卷烟零售客户数量也不同。而客户增长较多的线路，访销、送货压力就大，客户增加较小的线路，访销、送货压力就小。所以造成部分线路送货压力过大，同时，又有部分线路的物流资源处在空闲状态的现象。

不合理配送的表现形式

资源筹措不合理。配送是通过筹措资源的规模效益来降低筹措资源成本，从而取得优势。

库存决策不合理。会增加客户实际平均分摊库存负担，也会使社会财富积压，造成浪费。

价格不合理。配送的价格应低于客户自己进货、提货、运输、入库之成本总和。

配送与直达的决策不合理。一般的配送总是增加了环节，批量大的商品由供应商直接送货更经济。

送货运输不合理。车辆达不到满载、即时配送过多、过频、对流、迂回、無效、重复等运输都不合理。

经营观念不合理。经营观念不合理会损害配送企业的形象，配送优势也无从发挥。

卷烟配送线路优化难点及具体措施

卷烟配送线路优化难点。为了从根本上解决阻碍公司卷烟营销发展的问题，公司专门召集了全部卷烟营销战线的相关人员进行了深入的交流。

电访情况：按照国家局对于电访员工作的规定，一个电访员一天可以访问130户零售客户，按说现在公司有1300多个零售客户，按照分三批进行访销的方式一天平均有430多户，公司的12名电访员，应该能够完成访销任务。但是，由于一、四访销日和二、五访销日中访问的客户在客户总数中占据了较大的比重，每逢这几个工作日，我们都要加班加点进行电访，才能保证百分之百的拜访当日全部的零售客户。要完成卷烟销售任务难度相当的大。”

配送情况：公司的卷烟销售时大时小：有的时候车辆要超载行驶，在个别特殊的时候还要在市场和仓库跑两趟。但有些时候，有部分的车辆却基本没有什么装载，在跑‘空车。就拿周五来说，跑城网的车由于送货的对象基本是四类户，一辆车拉上30-40万支烟就跑上一趟，但是跑县上的辆车，单单在路上就要消耗接近3-9个小时的时间，卷烟配送量大又要在不同的县之间迂回送货，压力相当大。

卷烟销售情况：随着公司客户数的增加，公司的货源分配在市区客户和县区客户之间的分布不均横程度加大：在对市区进行电访销售时，每天430多万支的销售计划基本上是可以保证全部完成的。而在对县区的电访销售中这个比率则基本在50-60%之间徘徊，日销售变化量太大。”

只有从公司的卷烟配送方式上动手，优化工作方法，理顺货流通道，将线路精确到户，本着均衡分配，效率最优的原则，进行单车运输总量的测定，将送货线路进行调整。

卷烟配送作业的执行

配送计划的执行

按配送计划组织进货。当配送点库存商品数量不足或不符合配送计划时，要根据配送计划组织进货。

配货发运。仓储理货部门按配送计划将客户所需的商品进行分货、加工和配货，进行适当的包装。按配送计划将各客户的商品组合、装车和发运。

送达。安全、经济、高效地将商品送达客户，并由客户在回执上签字，交财务部门结算。

实施及时化作业JIT（Just ln Time）。配送中心及时化作业是指商品适时、实时和即时地调配，不超前、不等待。

配送中心及时化作业：生产供应及时化；传递信息及时化；送达及时化；库存管理及时化。

卷烟配送线路优化的实施。为了有效地降低了物流配送成本，不断提高了配送效率，按照“突出服务、注重效率、优化流程、提高素质”的要求，结合自身实际，积极探索，挖掘潜力，充分利用高科技手段，积极对配送线路进行合理优化整合，特制定送货线路优化管理办法，具体如下：

线路优化实施的基本原则：科学分析，注重实效的原则。操作便捷，可行性强的原则。优化配置，节约成本的原则。安全及时，优质高效的原则。

确定目标：以效益最高为目标的选择，计算时以利润的数值最大为目标值；以成本最低为目标的选择；以路程最短为目标的选择；当成本与路程相关性较强时，以吨公里最小为目标的选择，在“节约里程法”的计算中，采用这个目标。

配送绩效估

配送绩效评估可以通过人员利用率、车辆利用率等评估指标来反映。

人员利用率。评估配送人员的工作分摊（距离、重量、车次）及其作业贡献度（配送度），以衡量配送人员的能力负荷与作业绩效，确定是否增添或减少司机人手，在保证安全驾驶和成本控制之间取得平衡。

人员利用率可以用以下指标评估：

人均配送量人均配送量=配送量/配送人员数

人均配送体积重量人均配送体积重量=配送总体积重量/配送人员数

人均配送距离人均配送距离=配送总距离/配送人员数

人均配送吨公里人均配送吨公里=配送总吨公里/配送人员数

人均驾驶时间人均驾驶时间=总配送驾驶时间/配送人员数

车辆利用率。评估和设置最佳的配送车辆产能负荷，以避免折旧、损耗速度过快，以及可能发生的额外成本（过高的维修费、耗油费），并用来判断是否应增减送车数量。车辆利用率可以用以下指标评估：

平均每台车配送金额平均每台车配送金额=配送总金额/总配送车辆数总配送车辆数=自有车数+外用车数

平均每台车配送吨公里和平均每台车配送距离平均每台车配送吨公里=配送总吨公里数/总配送车辆数

平均每台车配送距离=配送总距离/总配送车辆数

满载车次比率满载车次比率=满载车次/总配送车次此指标反映对车辆的空间利用率。

空车率空车率=空车行驶距离/配送总距离

物流中配送路线选择的优化分析 第4篇

物流配送是物流系统中一个重要的环节,是物流节点送达收货人的过程。满足货运要求的前提下,如何选择配送线路是非常重要的,线路优化的目的在于保证运输安全的前提下,使配送线路和运输时间最优。

货物配送的重点就是如何将车辆进行有效利用,使得在配送时间和距离都相对最优的情况下配送到客户手中。由于规定了装卸点位置,力求多装快跑,节约时间和费用,提高效率,最经济就是两点间最佳运行路线。采用运筹学方法统筹考虑配送路线和配送时间,寻求最经济运行线路是非常必要的。本文应用相应算法并通过对济南市区配送线路的调查,计算相应的最佳配送线路,并进行对比说明一定问题。

1 线路优化方法概述

假设某配送中心负责b个接货点V*=｛v1,v2,…,vb｝,v0为配送站,G=0V,E,W0由城市道路构成的网络图,V=V*∪Y｛v0｝,E,W分别表示城市道路构成得边集,以及道路长度(或时间)构成的权集。

这类问题可用动态规划方法求解:第一步,将问题划分为m个阶段(阶段数划分根据接货点数而定);第二步,状态变量（vj,S）,vj∈Vm,vj表示送货车从v0走到vj,S表示到vj之前所经过的接货点集合,S⊆Vm;第三步,此处决策表示由一个接货点vj走到另一个接货点vj;第四步,最优指标函数,其中,S／｛vi｝表示除i之外的接货点,｜pij｜表示vi和vj两点间最短距离;边界条件为f0（vj,φ）,=｜p0j｜,j=1,2,…,m。进而求得来回且经过要求的点,使得路程最短。

2 实际中配送路线的线路优化

现有批娱乐设备,打算由运输车从济南长途汽车总站配送到大明湖、趵突泉和千佛山三个旅游景点,并回到长途汽车总站,试计算一条最短配送路线使得来回所走的路程最短。我们经过实际测算得到图1。

对图1进一步说明如下,v0:长途汽车总站,v1:三孔桥,v2:天桥,v3:人民商场,v4:大明湖,v5:趵突泉,v6:省中医,v7:青龙桥,v8:千佛山。针对上述路线图,求配送车从v0(长途汽车总站)出发途经Vm=v4,v5,v8返回v0,求最短环游路线及路径。

解依据动态规划方法原理,由边界条件可知:

当K=1时:

当K=2时:

当K=3时:

由此,通过动态规划的追溯方法得到由v0出发配送货物到v4,v5,v8这三个配送点,并最终回到v0出发点,这条路线的路程最短的最优路径,即距离17.49km,这条路线为:

上述路线说明,配送车按照上述路线行走,使得配送线路的路程最短。

3 实际中配送时间的线路优化

3.1 配送时间调查表的绘制及计算。

对于上述线路图1,通过浮动车法并应用相应公式计算各段路程时间。首先对长途车站到天桥间距离l为1.42km的线路进行调查,并绘制调查记录表,表1中各列含义为:T:出发时间,t:行程时间,X:迎面驶来的车辆数,Y1:超越测试车的车辆数,Y2:测试车超越的车辆数,Y:超越测试车车辆数与测试车超越车辆数之差,且表中序号1~6表示测试车向南行驶,序号1′~6′表示测试车向北行驶。调查表如表1。

浮动车法调查计算表如表2。

(1)先计算向南行情况

(2)再计算向北行情况

计算由长途车站到天桥时间为4.48min,而返回的时间为4.62min,取平均值当作行程时间为4.55min。

3.2 配送时间网络图的建立及计算。

图2中各节点与图1中相同,同样应用浮动车法求得了其他路段的行程时间,如图2所示。

由v0配送到v4,v5,v8三个配送点,并回到v0,这条路线的时间最短为33.41min,最佳配送路径为:

上述路线说明,配送车按照上述路线行走,使得配送线路的配送时间最短。

4 配送路线与配送时间类比

经计算得知若按最短距离行走,路线长度为17.49km,但花费的时间是64.65min。而按最短时间为33.41min行走的路线长度为23.41km,显而易见,如果按最短距离行走,虽然距离比按最短时间行走少了5.92km,但时间却多花费了31.24min,时间也是效益,节省时间也相当于节约成本,完全可以利用多花费的时间去再配送一趟物品,这样虽然多跑了路线,但却大大提高了车辆的利用率,节约了配送成本。

对于网络优化问题,由路程和时间求得最佳路径是不尽相同的。因此,在生活实践中应综合考虑时间及路程的最优问题,有利于提高车辆的利用率,降低运输成本,使运输效率达到最高。

5 结束语

配送线路优化能有效提高企业的服务质量、降低成本,充分考虑时间和路程,效果更加明显。因此,配送线路的优化研究对于发展城市的现代物流业和提高企业的核心竞争力具有重要的指导意义。

参考文献

[1]池洁,李莉.物流中配送区域与配送路线网络优化法[J].运筹与管理,2003,12(2):123-126.

[2]王炜,过秀成.交通工程学[M].江苏:东南大学出版社,2000:23-43.

[3]陈子侠.城市卷烟配送线路的网格划分算法[J].上海交通大学学报,2003(7):1013-1017.

沈阳成大方圆配送路线优化应用研究 第5篇

沈阳成大方圆医药配送中心位于浑南经济开发区, 对沈阳市的八十多家成大方圆连锁药店进行药品的配送, 选择合理的配送路线对公司节约配送成本、提高配送效率以及增强企业的核心竞争力有着举足轻重的作用。目前成大方圆医药配送中心存在配送路线不合理、车辆利用率不高、配送成本较高、配送效率较低、客户满意度不高等一系列需要改进的问题。

本文是以仓储与配送课程中的节约里程法为基础。节约里程法又称节约算法或节约法, 是指用来解决运输车辆数目不确定的VRP问题的最有名的启发式算法。利用节约法确定配送路线的主要出发点是根据配送中心的运输能力、各门店所能接受货物配送的时间、配送中心到各个用户以及各个用户之间的距离来制定, 使总的车辆运输的吨公里数最小的配送方案。基本思想是为达到高效率的配送, 使配送的时间最小、距离最短、成本最低, 而寻找的最佳配送路线。论文利用仓储与配送课程中所学到的专业理论知识, 对成大方圆医药配送中心配送现状进行调研, 并根据节约里程法的计算与研究, 提出相应的改进意见。具体研究内容包括:节约里程法的相关理论学习、利用GOOGLE地图和实地调研获取各门店到配送中心以及各门店间的距离、对沈阳成大方圆各门店进行考察获取各门店的药品需求量和接收货时间、利用SPSS进行数据整理分析、利用节约里程法进行相关计算并结合客观实际得出最优配送方案。

2 配送路线车辆优化调度模型

2.1 一般VSP模型

为构造数学模型方便, 将车场编号为0, 任务编号为1, , l, 任务及车场均以点i (i=0, 1, , l) 来表示。定义变量如下:

则可得到车辆优化调度数学模型如下:

模型中, cij表示为从点i到点j的运输成本, 它的含义可以是距离、费用、时间等, 一般根据实际情况确定, 可同时考虑车辆数和运行费用。如下确定:

(1) 当i为车场时, 包括固定费用和运行费用:

(2) 当i为任务点时, 只有运行费用, 即

其中, c1为相对于运行时间的费用系数;c0为车辆的固定费用, 即增加一辆车的边际费用。一般认为, 派出一辆车的固定费用远远高于车辆行驶费用, 因此该模型是在极小化车辆数的前提下, 再极小化运行费用。减小c0的值将会使使用的车辆数增多, 而线路长度缩短。若令c1=0, c0>0, 则模型目标是使用的车辆数最少。

2.2 时间窗VSP模型

设完成任务i需要的时间 (装货或卸货) 表示为Ti, 又设任务i的开始时间需在一定的时间范围[ETi, LTi]内, 其中ETi为任务i的允许最早开始时间, LTi为任务i的允许最迟开始时间。如果车辆到达i的时间早于ETi, 则车辆需在i处等待, 如果车辆到达时间晚于Lti, 任务i要延迟进行。求满足货运要求的费用最少的车辆行驶线路。此问题称之为有时间窗的车辆优化调度问题。

以si表示车辆到达点i的时间, tij表示车辆由点i行驶到点j的时间, 一般应有以下关系式:

3 配送路线优化

成大方圆医药配送中心是我校物流管理专业校外实习实训基地, 承担着沈阳八十多家成大方圆连锁门店医药配送的重要任务, 企业能否及时、准确、高效的完成每天的配送任务直接影响到各连锁门店的销售业绩, 影响着沈城老百姓的身体健康。目前成大方圆医药配送中心还是采用传统的按行政区分区的配送方式进行药品的配送, 以成大方圆苏家屯配送中心为例, 该配送中心需要配送医药地点分别为三和店、枫杨路店、雪松店、苏白路店、玫瑰店、月季店、陈相店、白清店以及特药桂花店等9个门店, 存在配送路线不合理、车辆利用率不高、配送成本较高、配送效率较低、客户满意率不高等几个方面的问题。

(1) 配送路线设计方面:配送行驶里程过大、路线复杂甚至出现路线迂回现象, 而有的配送量较小, 造成车辆配送里程浪费现象。

(2) 配送成本方面:由于各个配送路线的配送量的不均衡, 个别运输里程较长, 个别配送路线的迂回, 配送车辆的增加等问题导致配送成本增加。

(3) 客户满意度:成大方圆医药配送中心在配送过程中准时性较差, 经常会出现配送延误的现象, 导致各门店的药品配送不及时, 药品缺货的现象, 这就造成了很多客户的不满。

(4) 配送效率:现阶段传统的行政区分区配送方案造成了配送效率的低下。例如某一家门店由于自身原因无法正常接货, 而造成其它门店的配送延迟, 这样就会造成配送效率较低。

(5) 车辆利用率方面:目前的配送方案使得有的车辆配送压力较大, 而有的车辆由于配送量较小, 远远达不到车辆的额定载重量和额定载重容积, 无法提高车辆的使用效率。

(6) 灵活性:现阶段成大方圆配送中心采用小型货车进行配送, 市区配送在时间上受到禁行的制约, 很难完成紧急配送的任务, 灵活性较差。本论文特选取上述门店作为研究对象, 利用配送路线优化模型对其配送路线进行优化, 各配送点之间的距离如表1所示, 各配送点的货物运输任务及要求如表2所示。

单位:km

经过配送路线优化软件优化后, 得到结果如下所示。

4 优化结果分析

经过配送路线优化调度系统优化后的配送与以前的传统配送相比, 主要有以下优点:

(1) 经过综合考虑路线的复杂程度后, 可以提高配送的及时性, 提高顾客满意度;

(2) 多家集中配送的方式可以降低配送成本, 为企业赢得更多利润;

(3) 可以根据路线的实际交通情况, 及时调整配送路线, 提高配送的机动灵活性;

(4) 能最大程度地满足客户的需求。

摘要：通过沈阳成大方圆配送中心现状配送情况调查, 结合配送路线优化调度模型, 对成大方圆苏家屯配送中心配送路线进行优化研究, 研究证明, 优化后的配送路线可以提高配送的及时性、提高顾客满意度、降低配送成本以及可以提高配送的机动灵活性。

关键词：配送路线车辆优化调度,时间窗,物流配送

参考文献

[1]李化.北京通远企业配送供应链设计与线路优化研究[D].沈阳:东北大学, 2007, (8) .

[2]翁心刚.物流管理基础[M].北京:中国物资出版社, 2006, (6) .

[3]黄中鼎.现代物流管理[M].上海:复旦大学出版社, 2006, (2) .

配送路线优化 第6篇

关键词：配送路线,优化,描述法,节约法,EXCEL

0 引言

美国物流管理协会(Council of Logistics Management)把物流定义为迎合顾客需求而对原材料、半成品、产成品以及相关信息从产地到消费地高效率、低成本流动和存储而进行的规划、实施和控制过程。并且认为一个典型的物流系统组成要素包括:客户服务、需求预测、分拨系统管理、库存控制、物料搬运、定单处理、零配件和服务支持、工厂和仓库选址、区位分析、采购、包装、退货处理、废弃物处理、运输管理、仓储管理。从中我们可以看出运输时是物流决策的关键所在,除了采购成本以外,一般来讲,运输成本比其他任何物流活动的成本所占的比重都高。其中配送路线的选择和优化是运输决策中的一项重要决策。

尽管路线选择问题种类繁多,但我们可以将其分为几个基本类型:一是起点和终点不同的单一路径规划:二是多个起点和终点的路径规划:三是起点和终点相同的路径规划。

起点和终点不同的单一路径规划这类运输路径规划问题可以通过特别设计的方法加以解决,最简单最直接的方法就是最短路径法;多个起点和终点的路径规划这类问题经常发生在多个供应商,工厂或仓库服务于多个顾客的情况下,可以用一类特殊的线性规划算法,即运输方法来解决;起点和终点相同的路径规划这类问题在企业拥有自己的运输工具时就相当普遍了。

在这篇文章里,我们将介绍起点和终点相同的路径规划的这类问题。

1 提出问题

首先我们来看一个具体的问题,某物流公司有一配送中心(P)就有右图形状的配送路线。A~J表示收货站,括号内的数据为发送量(吨),路线上的数字表示道路距离(公里)。这时,为使行驶尽量少,应该如何去求配送路线?假设能利用的车是2吨和4吨两种,并限制车辆一次运行的初步距离在30公里内。

该问题在起点和终点相同的路径规划的这类问题中具有代表性,这类问题的优化方法有扫描法和节约法。

扫描法的步骤为:(1)在地图或方格图中确定所有站点的位置(含仓库)。(2)至仓库始沿任一方向外划一条直线,沿顺时针或逆时针方向旋转该方向直到与某一站点相交。考虑:如果在某线路上增加该站点,是否会超过车辆的载货能力?如果没有,继续旋转直线,直到与下一个站点相交,再次计算累计货运量是否超过车辆的运载能力(先使用最大的车辆),如果超过就剔除最后的哪个站点,并确定路线。随后,从不包含上一条线路上的站点开始,继续旋转直线以寻找新路线,继续该过程直到所有站点都被安排到路线中。(3)排定各路线上每个站点的顺序使行车距离最短,排序时可用“水滴法”或求解“流动推销员”问题的任何算法。

节约法是由克拉克·怀特发现的,它能够灵活地处理许多现实中的约束条件,对站点数量不大的问题能够较快地算出结果,且结果与最优解很接近,该方法能过同时确定路线和经过各站点的顺序。节约法的目标是使所有车辆的行使总里程最短,并进而为所有站点提供运输的车数最少。该方法首先假定每一个站点都由一辆虚拟的卡车提供服务,随后返回仓库,如右图所示。

这时的路线是最长的,下一步将两个站点合并到同一条行车路线上,减少一辆运输车,相应地缩短运输距离,不过合并一定要注意满足约束条件。合并后缩短的距离减少了d AO+d OB-d AB。只要条件满足就可以继续合并,直到所有的站点的路线都完成。

2 用EXCEL辅助解决问题

对于上面的具体问题的分析步骤如下:

第一步:绘出最短距离距阵图,从配送网络图中计算出配送中心与收货点及收货点之间的最短距离矩阵:

用EXCEL的求解方法如下:

用FLOYD算法需要进行11步迭代计算,令该网络图的全矩阵为D (dij)n×n,当两点间没有直达路时,dij为无穷大,这里令dij=100足以解决问题。算法基本步骤为:

(1)输入权矩阵D(0)0=D

(3)中元素就是从配送网络图中计算出配送中心与收货点及收货点之间的最短距离矩阵。

(4)D0为权矩阵,数据要自己输入,D1到D11为每步迭代中产生的矩阵,D11为从配送网络图中计算出配送中心与收货点及收货点之间的最短距离矩阵,F0到F10为辅助矩阵,他们在表格中位子如下:

根据FLOYD算法,下面介绍用EXCEL的分析步骤:

(1)建立结构。

(2)输入权矩阵D0的数据。

(3)选中矩阵D1中B17单元格输入公式“=IF(B3>P3,P3,B3)”,当鼠标移至单元格右下角时变成实心加号,此时按住左键,朝各个方向拖拉可以将整个矩阵用公式覆盖,这时你可以点击该矩阵内的任一单元格,如单元格E21就会显示公式“=IF（E7>S7,S7,E7）”。

if!"函数中有三项,第一项为逻辑运算式,如果它的值取true函数就返回第二项值,否则就返回第三项值,用以计算。

选中D1中的公式区!B17∶L27",用Ctrl+C复制,然后用Ctrl+V将其中的公式粘贴到D2到D11的对应公式区中。

(4)对辅助矩阵Fi i=!1,…,10",进行从F0到F10的依次计算。这里只介绍F0,其他的依此类推。

对于F0:

(a)先将D0的第一行的数值赋给F0的横填充区,将D0的第一行列的数值赋给F0的竖填充区,可先赋一个值,然后进行拖拉;要是对于Fi,就要将Di的第i+1行和列的数据分别赋予Fi的横填充区和竖填充区。

(b)在o2单元格中填入公式=n2+o1;要是对于Fi就要在对应的单元格中填入公式=该单元格左边的单元格+该单元格上面的单元格。

(c)用模拟运算表进行求和运算:选中黑框内区域。

在“数据”菜单中选择“模拟运算表”项,会弹出下图的对话框,将o2单元格左边的单元格填入到“输入引用行的单元格”,将o2单元格上边的单元格填入到“输入引用列的单元格”,然后按确定,这样就得到矩阵F0;对于Fi可以对应操作。

当从F0到F10都运算好之后,就会得到从配送网络图中计算出配送中心与收货点及收货点之间的最短距离矩阵,以上完成了第一步。

第二步:绘出节约里程项目图,从最短距离矩阵中计算收货点相互间的节约里程。将最短路矩阵的第一行和第一列复制到行竖填充区中,并在单元格B2内填入公式,用模拟运算表进行求和运算的到下面表格:

然后将矩阵中的数据与最短距离矩阵D11中的数据对应相减,就得到节约里程项目(图中三角形部分)。

第三步:节约项目的分类,把节约项目有大到小顺序排列。如下表:

第四步:组成配送路线,从节约项目表中,按节约里程大小的顺序组成路线图。

(1)初次解。

线路数:10总行走距离:148公里车辆台数:2吨车10台

(2)二次解。按节约里程由大到小的顺序,连接A-B,A-J,B-C连接线。

线路数:7总行走距离:109公里车辆台数:2吨车6台4吨车1台

(3)三次解。其次,节约里程最大的是C-D和D-E。C-D和D-E两者都有可能与二次解的线路甲相连接,但由于甲的车辆载重与行走距离有限,不能再增加收货点,为此,略去C-D而连接D-E。

线路数:6总行走距离:99公里车辆台数:2吨车5台4吨车1台

(4)四次解。接下来节约里程最大的是A-E和E-F。由于A已组合在完成的线路甲中,所以略去A-E而将E-F连接在线路乙上。

线路数:5总行走距离:90公里车辆台数:2吨车3台4吨车2台

(5)五次解。按上面的方法继续即得到五次解。

线路数:4总行走距离:85公里车辆台数:2吨车2台4吨车2台

(6)六次解。按上面的方法继续即得到6次解。

线路甲:4吨车总行走距离:27公里装载量:3.6吨

线路乙:4吨车总行走距离:30公里装载量:3.9吨

线路丙:2吨车总行走距离:23公里装载量:1.3吨

3 结束语

在这篇文章里,我们介绍了起点和终点相同的路径规划的这类问题。用EXCEL工具来辅助配送路线的选择问题的决策,能够达到比较好的效果。EXCEL在管理科学领域的应用很多,如线性规划、运输问题、指派问题、网络最优化问题、项目管理、库存管理、预测、排队论和计算机仿真,等等。运用EXCEL建立模型,求解模型,能对管理者的决策提供很好支持。

参考文献

[1]Ronald H.Ballou(美).企业物流管理——供应链的规划、组织和控制[M].王晓东,胡瑞娟,等译.北京:机械工业出版社,2002:145-197.

[2]弗雷德里克.S.希利尔,马克.S.希利尔,杰拉尔德.S.利伯曼(美).数据、模型与决策[M].任建标,译.北京:中国财政经济出版社,2001.

[3]胡运权.运筹学教程[M].北京:清华大学出版社,2000:241-242.

配送路线优化 第7篇

随着城市发展速度的加快, 生鲜蔬菜的需求也大大增加。徐州市正处于车辆高速扩展及房地产行业的高速发展阶段, 市区批发市场的地理分布格局逐渐稳定, 市场80%分布于三环路以外, 主要分布于城市环路与放射线交叉或者衔接高速道路的地区, 包括七里沟蔬菜批发市场、淮海蔬菜批发市场、铜山县蔬菜批发市场、丰县蔬菜批发市场、贾汪蔬菜批发市场、风华园蔬菜批发市场。

根据六大批发市场蔬菜交易量占全市交易总量的比例, 结合批发市场周边交通情况和道路通行量, 淮海蔬菜批发市场是徐州市最大的蔬菜流通批发市场, 承担着约70%的蔬菜供应, 其生鲜蔬菜配送的模式主要有直销型、契约型和联盟型三种。在联盟型配送模式中, 徐州市区的蔬菜批发市场 (七里沟蔬菜批发市场、淮海蔬菜批发市场、铜山县蔬菜批发市场、丰县蔬菜批发市场、贾汪蔬菜批发市场、风华园蔬菜批发市场) 和零售终端 (易初莲花、大润发、家乐福、沃尔玛、新一佳) 处于模式的核心地位, 其他的蔬菜生产商、批发商、运输商、加工保鲜企业等处于从属地位。近年来此配送模式迅速发展起来, 但仍然存在以下问题:

1.1缺乏低碳配送“最后一公里”的意识。为了提高自身市场的竞争能力, 徐州现有的配送企业往往只追求配送速度和保障货物安全, 忽略了节约社会效益, 尤其是配送过程中, 需求点都相对分散, 配送之间缺乏有效的合作, 导致在“最后一公里”乃至整个配送系统中忽视“最后一公里”的能源节约效益和低碳化。

1.2生鲜蔬菜配送网络布局不合理。立足于徐州目前的配送网络, 多数配送企业还从事单一功能的配送, 没有形成与现代化城市配送网络相匹配的网络布局, 不可避免地存在物流服务功能不全面, 增值效益低, 运输路线重复交错等问题, 从而造成蔬菜大量损耗, 制约经济效益的增加以及配送过程中碳排放量超标。

1.3市区交通日益拥堵、超市分布街区化是摆在生鲜蔬菜“最后一公里”配送最突出的难题。虽然徐州市交通局通过发放特殊时段车辆通行证来缓解交通压力, 但仍然无法协调配送蔬菜车辆出现的重复交错运输、无效率运输等不合理情况, 对周边交通状况形成较大压力, 配送标准化程度难以提升, 碳排放量居高不下。

1.4 相关政策支持不足。徐州作为全国重要的交通枢纽之一, 想要形成完整成熟的生鲜配送网络, 需要政府大力支持为其发展创造良好的外部环境。徐州市交通局对蔬菜配送车辆都有严格的区域限制, 基本上都不能进入徐州的市中心, 造成生鲜配送车辆只能绕道配送或将厢式货车的货物化整为零, 采用面包车运输, 由此造成配送效率的低下和装卸搬运过程中的损耗, 也在无形中增加碳排放量。

2 基于带时间窗约束下的生 鲜蔬菜配送车辆路线优化模型

徐州市生鲜蔬菜配送路径优化模型可以描述为:在七里沟生鲜配送中心和易初莲花、大润发、家乐福、沃尔玛和新一佳这五所大型超市的地理位置已知的情况下, 调配多台配送车辆从七里沟生鲜配送中心出发, 为易初莲花、大润发、家乐福、沃尔玛和新一佳这五所大型超市提供配送服务。其中, 各个超市的需求量、期望及可接受配送时间已知, 配送车辆的载重量及最大行驶距离已知, 且运输工具为配备有冷冻、冷藏设备的货车, 要求合理安排各配送车辆的客户群体, 制定有效的配送路径。在保证产品需求量、时间窗、有害气体排放量总体不变的前提下, 各蔬菜批发市场应该尽可能地实现总配送成本最小化。其中配送成本主要包括运输成本、货损成本、能源成本和固定成本。

2.1 为了将问题抽象为数学模型, 先假设如下

2.1.1本文以七里沟生鲜配送中心和易初莲花、大润发、家乐福、沃尔玛和新一佳这五所大型超市生鲜蔬菜低碳、低成本、低能耗的配送问题作为实证研究对象。

2.1.2配送车辆车型统一且无超载现象。在城市物流运输中, 大型货车所能行驶的道路极其受限, 且制冷条件较差, 对于短距离运输来说, 中型货车的应用更为广泛。七里沟拥有一定数量的中型货车, 车辆的运输规格与型号一致, 且配送速率为常数, 保持固定不变。在徐州城市物流环节中, 交警对于货车超载的监管更为严格, 且从自身交通安全角度考虑, 货载量应该严格控制, 中型货车的生鲜蔬菜运输量不得超过2.5吨。

2.1.3配送路径和配送车辆一一对应。由于七里沟生鲜配送中心距离蔬菜批发市场和各家连锁超市的距离都不远, 所以补货量不大, 每条路径安排一辆车即可, 同时, 一辆车也只为一条配送路径服务, 并且每辆车可为多个客户服务, 每个客户只能被一辆车服务。

2.1.4全封闭式配送车辆管理。配送车辆在完成生鲜蔬菜配送任务后, 立即返回七里沟生鲜配送中心进行车辆清理和维护。

2.1.5地理位置及需求量均已知。在徐州市的生鲜配送过程中, 七里沟生鲜配送中心和五家大型连锁超市的地理位置是已知的, 由此也就可以知道配送中心到个超市的距离、各超市之间的距离。同时, 由于各家超市的订单需求量也会提前几天汇总到配送中心, 以便进行备货和配货工作, 不需要配送中心进行预测。

2.1.6客户需求必须保障。超市对生鲜蔬菜的需求分为准确性、时效性和安全性三方面, 准确性即是指配送的生鲜蔬菜尽量避免出现货差, 种类和数量须与超市提供的订单相一致, 时效性即为送达时间不应超过超市可接受的时间范围, 并尽量做到在客户期望的时间段将生鲜蔬菜送达各大超市。

2.1.7各路段时耗已知。徐州市生鲜蔬菜的配送时间集中在凌晨三点至早上七点, 几乎不存在交通拥挤问题, 按照交通规定进行配送即可, 所以, 配送车辆在各超市之间、超市与配送中心之间行驶所需时间范围是可以根据以往经验进行判断的, 能保证在该时间段内车辆可通过该路径的概率超过95%, 降低配送过程中的油耗、时耗以及配送过程中有害气体排放量。

2.1.8本文假设在整个蔬菜运输过程中, 车辆的运输温度恒定不变, 且生鲜蔬菜的腐坏与运送时间密切相关。

2.2 数据处理

以徐州市南三环路段为例, 假设路网为方格路网, 且左右对称。其中, 承担单一配送服务的5个超市分别为易初莲花超市、大润发超市、家乐福超市、沃尔玛、新一佳超市, 配送的生鲜蔬菜保存期限为24小时, 产品随时间的变质函数为:Qi′=Qie-t/200, 配送温度为0℃, 售价平均为10元/件。运送车辆的容量为300件, 车辆平均行驶速率为60公里/小时, 单位里程的运输成本为2.5元 / 公里, 车辆固定成本约为150元/次。徐州市主要由6个蔬菜批发市场和5个连锁超市组成的市场区域, 在传统的物流配送模式下, 完成1次配送至少需 (6+5) ×2=22条线路, 即需要11辆货车在配送点和需求点之间进行往返配送。

注:1.车辆的最大运载量 2.5 吨;2.单位里程的运输成本为 2.5元 / 公里;3.车辆固定成本约为 150 元/次。

任一家连锁超市的潜在需求量至多是配送车箱体容积的2/5, 且车辆行驶距离不小于10公里, 在此约束条件下随机产生各连锁超市生鲜蔬菜的潜在需求量。通过调研数据分析徐州市5家连锁超市数量与实际生鲜蔬菜配送的实际状况, 本研究命各5家连锁超市的地理位置在边长为10公里的正方形内产生, 七里沟生鲜配送中心的地理坐标是 (0, 0) , 且七里沟生鲜配送中心与其他5家连锁超市商定好的配送时间窗[tai, tbi]处于早上七点至十二点之间, 且配送时间窗长度均为30分钟, 即tbi-tai=30, 因此生鲜配送时间约束[tai, tbi]皆为[20, 300]。根据以往经验估算5家连锁超市的配送服务时间 (单位:分钟) 可由已知的连锁超市潜在需求量除以20。随机产生的顾客资料如表2所示, 优化结果分析如表3。

注:1.车辆的最大运载量 2.5 吨;2.单位里程的运输成本为 2.5元 / 公里;3.车辆固定成本约为 150 元/次。

计算结果显示, 要想顺利完成整项配送工作, 配送服务中心需要5量配送车, 其总运输成本为501元, 货损成本为30.4元, 能源成本为297元, 车辆固定成本为750元, 总成本为1578.4元。若采取传统的生鲜蔬菜配送模式, 完成1次配送至少经过22条线路 (往返) , 需要11辆货车, 运输总成本为1159元, 货损成本为54.4元, 能源成本553元, 车辆固定成本为1650元, 总成本为3384.4元, 节省了53.3%。通过上述比较可以看出, 本文采用带时间窗约束下的生鲜蔬菜配送车辆路线优化模型能够获得较优解。

3 结束语

生鲜蔬菜是人们日常生活的必需品之一, 向居民提供价格低廉、新鲜绿色的蔬菜也是创建和谐社会的关键。基于低碳视角下, 生鲜蔬菜配送过程在满足客户要求的时效性和安全性的同时, 徐州市还要合理规划蔬菜批发市场以及生鲜蔬菜销售网点, 降低流通成本, 实现蔬菜流通的渗透;进一步加大环城道路建设、公共停车场建设等公益性基础设施, 有效提高生鲜蔬菜装卸搬运作业效率, 减少生鲜蔬菜的间接运输成本;大力发展冷链物流, 减少生鲜蔬菜产后运输和跨季节储存损耗, 促进菜农的收入, 降低居民购买价格, 实现生鲜蔬菜“真正的新鲜”。

参考文献

[1]王海丽, 王勇, 曾容长.带时间窗的易腐食品冷藏车辆配送闯题[J].工业工程, 2008, 3:127-139.

[2]易兵.浅议低碳经济下的低碳物流[J].现代物流, 2010 (8) :70-71.

配送路线优化 第8篇

大多数节约算法在配送线路选择中的应用只考虑了路程长度, 即保证在运输工具载运空间满足的情况下使运输线路最短, 但是在日常实际决策过程中还要考虑到配送时间, 也就是在添加了时间窗限制条件下的配送路线的选优。因为时间效益已越来越受到了各企业的重视, 为了支持企业的竞争策略, 实现对客户的承诺, 必须保证物品在规定的时间内送到各客户企业不得延误, 本文旨在考虑时间窗限制条件下的配送路径如何应用节约算法来实现。

2. 问题的求解办法

2.1 问题的简化

一般说来, 客户点i的时间窗可设为[ai, bi], 时间窗可分为硬时间窗和软时间窗, 硬时间窗是指车辆在时刻bi之后到达客户点是不允许的, 若在时刻ai之前到达, 则等待;软时间窗是指允许车辆到达客户点的时间有所偏离, 但要根据所带来的不方便程度领受一定的惩罚。多数时间窗问题均为软时间窗问题, 但为了简化研究, 在本文中规定配送路径中各客户点所要求的时间窗均为硬时间窗。

以往用节约算法解决配送路径问题均利用最短距离表, 根据最短距离表计算出客户间的节约里程;但是在实际中, 配送过程费用和服务质量取决于时间与路程的综合因素, 所以应该在实施过程中综合考虑这两个因素, 可以采用以下指标代替客户点间的距离的措施: (1) 中间的过程指标用: (路长÷正常速度正常速度概率+路长÷非常速度非常速度概率) ;或者用: (非常速度路长÷非常速度+正常速度路长÷正常速度) ; (2) 如果服务需求稳定, 配送的起止时间固定, 则中间的过程指标用: (路程长度/平均车速) 。本文采用第二种措施, 并且为了方便计算, 不考虑货物装卸搬运等在客户点所耗费的时间, 即服务时间, 将其归并入固定端的路程耗费中。

2.2 节约算法的基本原理

节约算法是一种基于节约准则的逐步构解算法。

算法基本思想为:当将两条线路 (0, , i, 0) 和 (0, j, , 0) 合并成一条线路时, 则所带来的路程长度节约值为sij=ci0+c0j-cij;sij越大, 说明把i和j连接在一起 (即合并相应的两条线路) 会使总费用减少越多, 若根据sij的大小来构造线路, 就有可能得到总费用较小的解。

算法步骤为:

步骤1计算节约值。将起点分别与各客户点连接, 形成n条初始线路 (0, i, 0) , 计算节约值sij=ci0+c0j-cij, 并按从大到小的顺序排列。

步骤2寻找可行的最好合并。按照sij的上述顺序, 逐个进行检查, 若存在两条这样的线路, 一条包含弧或边 (i0) , 另一条包含弧或边 (0, j) , 且合并后能保持解可行, 则引入弧或边 (i, j) 将两条线路合并, 并删去 (i, 0) 和 (0, j) 。重复该步骤, 直到没有可合并的线路为止。

(注:表中时间单位均为分钟, 如 (20, 60) 表示ai为从某一特定时间开始算起经过了20分钟, bi为从所定特定时间开始经过了60分钟)

2.3 一个实例的设计和分析

设一配送中心向8个客户配送商品, 配送中心及客户间的最短时间距离及需求表, 如表1 (最短时间距离是由最短距离除以平均车速12 km/h得到的, 为了方便计算, 在表1中将最短时间距离都统一成了单位min) 。客户点的时间窗限制要求见表2。

假设配送的车辆最大载重为200t, 那么利用节约法求解的配送路线的步骤如下:

第一步:根据最短距离表, 利用节约法计算出用户间的节约里程, 并由大到小排列, 编制节约里程顺序表, 如表3。

第二步:根据节约里程顺序表和配送中心的约束条件, 制定配送路线。其具体步骤如下:首先选择最节约里程的路段 (6~7) , 然后是 (5~6) , 此时按顺序表本应把 (4~5) 添加到本条循环路线上来, 但由于57+16+56+92=221>200, 不满足配送车辆最大载重量限制条件, 故接下来选择 (3~5) , 然后是 (7~8) , 此时载重总量为192t, 由于在余下选择中没有满足条件的客户, 所以第一回合的配送线路为 (DC~3~5~6~7~8~DC) , 按照此种方法, 剩下的配送线路为 (DC~1~2~4~DC) , 载重总量为176t。

以上是利用标准的节约方法求解配送路线所得的结果, 但是要考虑到每个客户点所要求服务的时间窗, 故需要在原有方法上作一些改动, 添加新的检验步骤, 使得车辆配送路径问题和各客户点的时间窗限制条件的结合成为可能。

第三步:分别检验所求得的两条配送路线是否满足线路上各客户点的时间窗限制条件, 具体方法是:令线路上各客户点的时间窗为 (ai, bi) , 车辆由一点到达另一点所需的行驶时间为D, 在线路上按客户点的顺序分别计算为满足客户点时间窗需求的配送中心车辆出发时间窗, 然后求其交集, 若没有交集, 则说明此配送路线不满足时间窗限制条件, 需要进行分解修改。其中, 顺序求解各客户点配送中心车辆出发时间窗的方法是由该点的服务时间窗端点减去由配送中心到该点的时间, 即 (ai-∑Di, bi-∑Di) 。在本例中, 在线路 (DC~1~2~4~DC) 中, 客户点1对配送中心的车辆出发时间窗要求为 (20-12, 60-12) , 客户点2为[30- (9+12) , 60- (9+12) ], 客户点4为[40- (8+9+12) , 100- (8+9+12) ], 最后取三者交集得 (11, 39) , 即为满足本条线路上各客户点的时间窗限制, 配送中心也有一个出发时间窗 (11, 39) 。在线路 (DC~3~5~6~7~8~DC) 中, 按照以上办法, 求得各客户点对配送中心的车辆出发时间窗要求为 (23, 63) ∩ (19, 69) ∩ (23, 43) ∩ (49, 79) ∩ (39, 69) , 其中客户点6的限制为 (23, 43) 客户点7的限制为 (49, 79) , 两者并无交集, 故需要对此条线路进行调整, 调整办法是在原有线路中必须把客户点6和7分开, 最简单的办法是把原线路分为 (DC~3~5~6~DC) 和 (DC~7~8~DC) 两条, 当然也可以采用其他的线路划分, 在此不做进一步探讨。

3. 结论

配送路线优化 第9篇

发展市场经济, 流通极为重要。车辆的路线问题 (vehicle routing) 主要解决连锁商业系统中货物配送的车辆装载、车辆路线和人员配备等优化问题。针对车辆调度问题, 建立相应的数学模型、比较已有的车辆路线问题的相关方法在我国连锁商业配送过程中的应用效率和建立新的算法, 是非常必要且有重大商业价值的。TSP问题因其典型性已成为各种启发式搜索、优化算法的间接比较标准。因此, 快速、有效地解决TSP问题有着极高的理论及实际应用价值, 利用它解决物流配送路线问题依然是最有效、最方便、最可行的。

1 TSP问题的提出

在一组N个城市的集合中, 一个推销员从某一个城市出发, 拜访各个城市一次后回到原出发的城市, 限制条件为每个城市只能经过一次, 且必须都走过, 最后在各个符合条件的路径中找出最短的封闭路径。该问题称为TSP ( Travelling Salesman Problem) 问题, 又称为货郎担问题、邮递员问题、售货员问题, 是有名的N-P难题之一。要得到N个城市依次经历的最短路径, 应把N个城市所经过的路程相比较, 选出其中的最佳行进路线。

TSP问题描述十分简单, 简言之就是寻找一条最短的遍历n个城市的路径, 或者说搜索整数子集x={1, 2, 3, 4} (x的元素表示对n个城市的编号) 的一个排列∏ (X={V1, V2, Vn}, 使

undefined

取最小值。式中的d (Vi, Vi+1) 表示城市Vi到城市Vi+1距离。

2 TSP问题的常见解决方案

近年来, 解决TSP问题的方法主要有启发式算法、模拟退火法及遗传算法等。

(1) 启发式算法。

旅行商 (TSP) 问题是组合优化中最典型的NP-Hard问题之一, 目前关于该问题的启发式算法主要分为两类:环路构造算法和环路改进算法。对于第一类算法, 首次提出了在环路构造中成批加入顶点, 同时在构造过程对环路进行局部优化的思想, 由此得到了一种新的算法:SizeScale-Construct, 它的解质量极大地改进了现有的环路构造算法。对于第二类算法, 在分析局部最优解与全局最优解之间关系的基础上, 提出了另一个采用局部最优解的交集作为初始环路的新算法:SizeScale-Improve。实验结果表明, 该算法在解的质量和求解速度上都较大地改进了现有最好的环路改进算法;另一方面, 理论上对于最坏情况和平均情况时间复杂度的分析表明这两个算法是实用的。由于递归方法在处理问题时的简便, 本文采用递归程序解决TSP问题算法。

递归程序是直接调用或通过一系列的过程间接调用程序。但递归程序运行的效率一般都比较低, 因此应对递归程序进行优化。

(2) 模拟退火算法。

作为模拟退火算法应用, 讨论货郎担问题 (Travelling Salesman Problem, 简记为TSP) :设有n个城市, 用数码1, , n代表。城市i和城市j之间的距离为d (i, j) i, j=1, , n.TSP问题是要遍访每个城市恰好一次的一条回路, 且其路径总长度为最短。求解TSP的模拟退火算法模型可描述如下:

解空间:解空间S是遍访每个城市恰好一次的所有回路, 是{1, , n}的所有循环排列的集合, S中的成员记为 (w1, w2 , , wn) , 并记wn+1= w1。初始解可选为 (1, , n)

目标函数:此时的目标函数即为访问所有城市的路径总长度或称为代价函数:

undefined

我们要求此代价函数的最小值。

undefined

模拟退火算法的应用很广泛, 可以较高的效率求解最大截问题 (Max Cut Problem) 、0-1背包问题 (Zero One Knapsack Problem) 、图着色问题 (Graph Colouring Problem) 、调度问题 (Scheduling Problem) 等等。

(3) 遗传算法。

采用遗传算法求解货郎担问题 (TSP) 的应用程序是由选择、交叉、逆转和变异4个遗传操作及群体更新等主要算法模块以及诸如随机数发生器、控制参数输入、群体初始化、图文数据输出、译码、适应度计算等辅助模块组成的。在程序中, TSP问题的城市坐标是由随机数发生器产生的, 遗传算法的选择机制为比例选择机制, 交叉采用部分匹配交叉策略, 变异采用随机多次变换方式, 逆转操作采用单项连续多次逆转方法, 群体更新采用由覆盖的代间更新方式。程序的输入参数为群体规模、染色体长度、交叉概率、变异概率机、遗传世代数等5个遗传控制参数以及存储该程序运算结果的文件名。其中, 群体规模的取值范围为2100之间的任意偶数, 染色体长度 (TSP的城市数) 可取不大于100的整数, 交叉概率和变异概率的取值范围为[0.00, 1.00]。显示器输出的语文数据包包括交叉次数、变异次数、世代数、群体中的最大、最小及平均适应度、当前最佳路径的长度、程序运行时间等统计参数及当前最佳路径图;文件存储的数据包括TSP问题的城市位置 (平面坐标) 、历代最佳路径长度以及优化的最终结果等。

3 TSP在物流配送车辆运行路线中的应用分析

配货路线指从配货公司所在地出发, 走遍各公司, 又回到配货公司所在地的路线。

(1) 若配货汽车分3组送货, 试设计总路程最短且尽可能均衡的送货路线。

(2) 假定配货汽车在各大公司停留时间T=2h, 在各小公司停留时间t=1h, 汽车行驶速度为V=35km/h。要在24h内完成配货, 至少应分几组;给出这种分组下你认为最佳的配货路线。

(3) 上述关于T、t、V的假定下, 如果配货汽车足够多, 完成配货的最短时间是多少;给出在这种最短时间完成配货的要求下, 最佳的配货路线。

(4) 若配货汽车组数已给定 (比如3组) , 要求尽快完成配货, 讨论T、t和V改变对最佳配货路线的影响。

3.1 问题的假设

(1) 路况不考虑等级差别, 即可将所有路面状况视为相等, 车辆在所有公路上速度保持恒定。

(2) 交通情况不受影响, 即车辆在所有公路上都可以顺利通过。

(3) 各配货汽车组统一行动, 不可再分成小组进行配货。

(4) 对于某些至少要经过两次的大、小公司, 认为仅在第一次经过这些地点时停留, 以后再经过就不再停留。

(5) 对于某两个区域的大、小公司, 只要任一个配货汽车组停留过, 其它组经过时就不再作停留。

3.2 参数的说明

Pi:各配货汽车组的配货路程长度 i=1 2 3n。

ti:各配货汽车组的配货时间 i=1 2 3n。

n:组数。

B:距离均衡度函数。

b:时间均衡度函数。

3.3 模型的建立与求解

本题是一类图上的点的行遍性问题, 也就是要用若干条闭链覆盖图上所有的顶点, 使某些指标达到最优。本题所要求的分组配货的最佳路线, 与多旅行商问题类似, 也就是求m条经过同一点并覆盖所有其它顶点又使边权之和达到最小的闭链。旅行商问题都属NP完全类问题, 对于本题的规模, 要想求得真正的最优解是不现实的, 只能求得近似最优解。

(1) 第一问的求解。第一问要求设计分3组配货总路程最短且尽可能均衡的配货路线。设3组的配货路线长度从小到大为P1、P2、P3, 则我们要达到的目标为

min P1+P2+P3 (4)

min P3-P1 (5)

但是这两个目标函数是互相矛盾的, 即它们不可能同时达到最小。因此在求解时, 要折衷考虑。

具体求解步骤如下:①采用一定的分区原则将地图分成3个区;②按区寻找最小生成树, 并在其基础上求解最短回路;③求出每条回路的长度, 代入距离均衡度函数, 如果满足条件则终止;否则, 按调整原则将区域进行调整, 返回②。

(2) 第二问的求解。由于T=2h, t=1h, V=35km/h, 需访问的大公司17个, 小公司35个, 则在大公司、小公司总的停留时间为172+351=69h, 需在24h内完成配货, 若仍分3组的话, 平均每组只有1h的行路时间, 只能走35km, 无法在规定时间内走完所有的大、小公司。因此, 考虑行路时间, 至少要分4组。

与第一问类似, 设这4组的配货时间从小到大为t1、t2、t3、t4, 要实现的是下面两个目标函数

min t1+t2+t3+t4 (6)

min t4-t1 (7)

在具体求解时, 仍采用第一问中的分区域求区域内的最小生成树根据最小生成树找回路计算均衡度调整的方法。下面只对分区原则和均衡度函数作以下补充:①将原地图分成4个区;②分区时要尽量使各组的停留时间相等。可先将相对集中的大公司划为一个区, 兼顾大公司个数的均匀, 再通过调整小公司的划分来实现时间上的均衡;③均衡性的衡量采用时间均衡度函数B, 使B等于

undefined

当b0.1时认为是均衡的。

按照以上步骤, 采用计算机搜索的方法, 得到一组较优解, 括号中的点表示只经过不停留。

(3) 第三问的求解。若有足够多的配货汽车, 要求出完成配货的最短时间, 并给出在最短时间下的最佳配货路线。这是求点集的最小覆盖问题, 子集覆盖问题属于NP完全类, 无法在短时间内找到最优解。

可以求出配货距o点最远的大公司所需的最短时间Tmin, 这样, 其它各组的配货时间都不应超过Tmin。引入点权的概念, 若为大公司, 点权为2;若小公司, 点权为1, 即为在该点的停留时间。

diji:点到j点的最短通路长。

wi:i点的权。

ei:从o点到j点的最短时间。

在最短时间的限制下, 完成配货的最优路线应满足如下条件:①每个组的配货时间不能超过最短时间Tmin;②所有的点都应配货到, 不能漏点;③所需配货组数要尽量少。

(4) 第四问的求解。若配货组数已定, 则每组所用的时间为ti=xiT+cit+si÷V。

xi:第①组停留的大公司。

ci:第①组停留的小公司。

si:第①组的配送路线长度。

当T、t不变而V增加时, ti主要受V影响, 因此要求路线的均衡性比较好。这时需对xi、ci作调整, 对路程较长的组尽量考虑停留较少的小公司。

当V不变而T、t增大时, ti主要受xi、ci影响, 此时大公司、小公司分布的均衡性就显得十分重要。特别是大公司, T越大, 对大公司的均衡性要求就越高。各组的配送路线的均衡度可以差一些, 因为在T、t大到一定程度时, si÷V可忽略。

4 结束语

在启发式算法中, 递归程序一般都有很大的优化空间, 由于递归过程结构清晰, 程序易读, 而且正确性容易得到验证。因此, 利用允许递归的语言如Pascal 、C (++) 等进行程序设计时, 给用户编制程序和调试程序带来很大的方便。遗传算法是仿真生物遗传学和自然选择机理, 通过人工方式所构造的一类搜索算法, 从某种程度上说遗传算法是对生物进化过程进行的数学方式仿真。遗传算法作为21世纪关键智能计算之一将会在可计算理论和实际中得到更广泛应用。模拟退火算法的应用很广泛, 可以较高的效率求解最大截问题 (Max Cut Problem) 、0-1背包问题 (Zero One Knapsack Problem) 、图着色问题 (Graph Colouring Problem) 、调度问题 (Scheduling Problem) 等等。

参考文献

[1]姚新, 陈国良.进化计算研究进展[J].计算机学报, 2009 (18) .

[2]唐立新.旅行商问题 (TSP) 的改进遗传算法[J].东北师范大学学报, 2008 (7) .