配送路径优化范文

配送路径优化范文（精选11篇）

配送路径优化 第1篇

航空物流配送是指按客户的订货要求, 在航空物流中心进行分货、配货, 并将货物及时送交收货人的物流活动。送交收货人环节包括车辆选择及运输路线规划。目前, 国内航空货运配送环节, 由于路线规划缺乏优化选择, 使航空货运无法更好发挥快捷性优势。常用规划方法有:动态规划、分支定界、节约里程、扫描、贪婪算法及现代遗传、模拟退火、蚁群算法。其中, 遗传算法结合现代智能技术, 能适应航空物流多点配送的特点, 提高精确度。

二、航空货运配送规划

根据遗传算法基本理论设计适用于配送路径模型的遗传算法, 主要包括染色体编码与解码、初始群体、适应度函数、遗传等要素的设计。

1. 编码与解码及产生初始种群

假设配送中心有车辆k台, 客户点l个, 采用增加k+1个虚拟配送中心可形成一条长为k+l+1的染色体编码串 (0, i11, i12, …i1a, 0, i21, i22, …, i2b, 0, …, 0, ik1, …, ikc, 0) , 其中染色体相邻两个0之间表示一条子路径。将路径分隔符的0加入到染色体中, 所有路径中被访问的客户依次编码至一条染色体中, 可保证每个客户节点均被访问有且只有一次, 大大地简化了对模型约束条件的处理。

解码时, 初始化一条路径, 将染色体中的基因值顺序插入到当前路径中, 若一个基因值的插入导致该路径的负荷超过了车辆的最大容量或返回配送中心的时间晚于最晚返回时间, 则开始构建新的路径, 重复上面操作, 直至所有客户均被插入到路径中。

由于遗传算法搜索最优解不依赖于初始种群, 为使初始种群尽可能地均匀分布在整个解空间, 随机生成初始种群。

2. 选择

采用改进轮盘赌选择算子, 设种群大小为M, 父代种群Z={a1, a2, …, ai, …, aM}, 其中每个个体的适应度大小为f (ai) , 子代群体初始状态为X={}。

(1) 将所有个体按其适应度值f (bi-1) >f (bi) >f (bi+1) 进行排序;同时, 计算出父代种群中适应度最大个体k, 即f (ak) =max (f (a1) , f (a2) , …, f (aM) ) 。

(2) 计算出群体Z′中所有个体的适应度总和

(3) 计算每个个体被选中的概率

(4) 计算每个个体的累积概率

(5) 转动M轮轮盘。

1) 产生M个[0, 1]之间的均匀随机数r。如果r≤Qi, 则选择染色体bi, 否则, 选择第i个染色体bi (2≤i≤M) , 使得Qi-1≤r≤Qi。

2) 统计各区间ξ值ξ1, ξ2, …, ξM, 其中ξi是落在i号区域的随机数个数

3) 取最大的ξ值ξj=max{ξ1, ξ2, …, ξM}所在区间j对应的个体bj为本轮转动后所选中的个体Mi, 即

5) 若选出的个体数到达种群大小, 则转7) , 否则转1) 。

(6) 找出子代种群X中适应度最低个体m。

(7) 用个体k代替个体m。

(8) 存储所有新选出的个体, 并且返回。

3. 交叉

(1) 随机在父代个体中选择一个交叉区域, 如两父代个体及交叉区域选定为:A=“256|8437|19”, B=“359|4178|26”, 其中“||”表示交叉区域;

(2) 将B的交配区域加到A的前面, A的交配区域加到B的前面, 得两中间个体:A′=“4178|256843719|”, B′=“8437|359417826|”;

(3) 在A′和B′中, 自交叉区域后依次删除与交叉区相同的基因, 得到最终的两个个体为:A1=“843759126”, B1=“417825639”。

4. 变异

采用倒位变异算子进行变异操作, 随机选择一染色体的两变异点, 将变异区域进行倒位得到新的个体。倒位变异在进化过程中可对种群中的个体进行有效地调整, 防止早熟收敛问题, 改善遗传操作的全局寻优性能。

(1) 随机产生一个体temp=“9 2 5 8 7 3 10 4 6 1”和两变异点, 如2和3, 即temp=“9|2 5 8 7 3|10 4 6 1”, 其中“||”表示变异区域。

(2) 将变异区域基因按反序插入到原位置中得到新个体temp1=“9|3 7 8 5 2|10 4 6 1”。

5. 适应度

适应度是评价个体优劣和进行遗传操作的重要依据, 个体的适应度越大, 被选择到下一代的概率越大。设适应函数

zi为群体中第i条染色体对应的目标函数值, 反映了第i条染色体所对应的的配送总费用;fi为第i条染色体对应的适应度, 其值决定了该染色体产生后代的概率。

6. 终止规则

配送中, 可判断进化的代数是否为要求代数N, 若是, 则停止进化, 选性能最好的染色体所对应的配送路径集合作为所求VRPTW问题的最优解输出。反之, 继续执行进化运算。

三、结论

如何提高共同配送的路径分析论文 第2篇

1 共同配送的产生

共同配送是指“由多个企业联合组织实施的配送活动”。它最早来源于日本的连锁便利店7-11(Seven-Eleven)。早期日本7-11的供应商都有自己特定的批发商，每个批发商一般都只代理一家供应商的货物，如图1所示。供应商A只给批发商a发货，供应商B只给批发商b发货，供应商C只给批发商c发货，供应商D只给批发商d发货。这个批发商(批发商a，b，c，d)不仅是连接7-11门店及其供应商(供应商A，B，C，D)之间的纽带，同时也负责传递7-11门店和供应商之间的货物、信息和资金的责任。在这种配送模式下，批发商就相当于7-11门店的配送中心，它所要做的就是把供应商手中的产品迅速有效地运送到7-11手中。

随着7-11便利店销售额的增大，其货物的需求也日渐增多，规模也逐渐扩大，起初那种单个批发商零散式的配送已经无法满足7-11的需要。于是，7-11开始和批发商及部分生产商合作，建立了统一的集约化配送和进货系统，如图2所示。7-11将以往的各零散批发商整合起来，形成统一的特定批发商，货物再由特定批发商运送到各个7-11门店。在此，特定批发商充当着配送中心的角色。它既是供应商和7-11门店的货物传递桥梁，也是信息传递的重要纽带。在这种集约化配送系统之下，7-11摒弃了以往由多家批发商分别向各个便利店送货的方式，改由一家特定批发商在一定区域内统一管理该区城内的同类供应商，然后向7-11统一配货。由此，有效地降低了批发商的数量，同时也减少了配送环节，为7-11节省了物流费用。

在集约化配送系统经历一段稳定的运营期后，7-11发觉，被称为自己生存命脉的经营信息统统掌握在特定批发商手中。与其将命脉掌握在别人手中，不如掌握在自己的手中。于是，7-11夺回了配送中心的主动权。它成立了共同配送中心代替了原有的特定批发商，既而随时掌握在途商品、库存货物等情况，如图3所示配送模式。各个供应商(A，B，C，D)将自己的货物分别运送到共同配送中心，然后由共同配送中心统一配送到各个7-11门店中。就这样，共同配送系统浮出了水面。

2 目前我国的配送现状及存在问题

目前，我国的零售企业还都是些中小型企业，配送还处于货物少、批量频度不规律的状态。但是为了满足客户日益变化的需求以及尽量减少库存的目的，这些零售商通常都是采取小批量、高频度为特点的配送方式。由于没有充分的利用各个物流链节点企业的资源，久而久之，增加了企业的.物流成本。再者，当遇到商品种类及数量繁多或者交货期提前的情况，企业会为了满足客户要求，加快对店铺的零散配送，这势必将导致运输车辆的增多，造成城市交通的拥堵，严重至恶化城市的环境。针对以上目前物流配送所存在的问题，要想改变现状，我国也应当积极发展共同配送。

3 如何提高共同配送的效率

共同配送的优势可以归纳如下：

①减少道路车流量，改善交通运输状况。

②共同配送可以带来规模经济效益。

通过共同配送的实施，能够整合物流企业的功能和设施、信息设备、网络等资源，最终实现物流资源的优化配置。尽管共同配送有如前所述的优势，但是其配送效率也是发挥预期作用的关键因素之一。因此，本文从以下三个方面来阐述如何提高共同配送的效率。

3.1 从选择合作伙伴上来提高共同配送的效率

在实现共同配送的过程中会遇到很多困难。这些困难靠单方面努力是不够的，要靠合作伙伴，政府或地方公共团体等的大力支持。这其中，选择合适可靠的合作伙伴，不光能够保证合作企业的商业机密不被泄露，也是提高共同配送效率的重要手段之一。各物流企业配送的商品不同，比如食品、药品、日用百货等，不同的商品有不同的保存方式，也有不同的配送方式。因此，在配送上也存在一定的区别。同时，各企业的经营意识、客户分布等方面也存在着差异。这便造成各企业间的意愿很难达成一致。所以，在开展共同配送时，为了降低共同配送的难度和复杂度，应当增强共同配送的协调性，即应选择在配送商品的特性、保管和装卸特性、配送客户分布状态、物流服务水准、配送数量等方面有较大相似性的企业来参与共同配送。

3.2 从细心观察身边环境的变化来提高共同配送效率

准确地判断进货品种及数量是减少配送失误的一个指标。如果不能明确进货品种及数量，不但会对客户端、门店端造成损失，还会增加不必要的车流量造成环境污染。因此，正确地判断所需货物的品种及数量显得尤为重要。这其中的一个方法就是通过细心观察周围的环境变化来提高判断的准确率。

例如，根据天气预报来预测销售趋势。西方经济学中有一条和气象有关的定律：气象的投入与产出比为1∶98，即企业如果在气象信息上可以投资1元钱的话，那么它便可得到98元钱的经济收益。并且，在不同的市场环境下，经济回报率可能会更高。日本7-11就在这点上下了很大的工夫：7-11门店会根据天气情况预测每天的销售趋势。由于午餐、饭团和三明治等食品占据日本7-11每日销售额的一半左右，而这些商品的销售周期短，贩卖情形又和天气气候气温息息相关。因此，事先把握天气情况，是预订当日商品数量的关键，换言之，也是提高共同配送效率的方法。

再比如说，背景音乐的选择也大大地影响订货数量及销售额。在日本的很多家零售店里，背景音乐中常常会录制适时变换的问候语、促销活动的宣传话等等。在为顾客提供方便快捷的服务以外，还时刻提醒并诱导着顾客的消费趋向。这样对销售商来说，便于订货;对配送中心来说，也便于大批量统一运输，从而提高了共同配送效率。

诸如此类，零售商凭借通过细心观察顾客的需求动态并及时调整销售模式，或者通过有效地诱导、刺激以促进顾客消费动态等方式，准确判断出订货品种及数量进而能够实现共同配送的提高。

3.3 从加强物流科技含量上来共同提高配送效率

电子计算机的广泛应用不但促进了现代物流系统的发展，同时还加快了商品流通的步伐。在一些先进国家中，智能机器人、自动化立体仓库、自动化分拣系统、条码技术、扫描技术、电子数据交换系统(EDI技术)、地理信息系统(GIS系统)和全球定位系统(GPS系统)等现代化装备和高新技术已经在物流领域中得到了充分的应用，有利地实现了物流的标准化、智能化、规范化及自动化，大大地减少了人力，节省了时间 ，同时也大幅度地降低了人为失误产生的概率。

例如，在日本配送中心被广泛采用的流通van(即计算机增值服务网络)，是将制造业、批发业、零售业相关的商业信息，通过服务网络来互相交换的一种信息系统。配送中心通过流通van与制造商、批发商、零售商等联机，构成完整的信息网络，进行信息处理和交换。流通van监控着从接受订货到发货的整个物流流程，以确保实现准时配送，并合理控制商品库存，减少积压，有效地起到了“信息网络节点”的作用。通过对物流中心进一步地计算机化从而使共同配送业务更接近零损失，最终达到高效配送状态。

4 小结

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

当前配送线路的基本情况

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

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

分析问题：

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

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

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

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

不合理配送的表现形式

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

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

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

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

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

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

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

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

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

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

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

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

卷烟配送作业的执行

配送计划的执行

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

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

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

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

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

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

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

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

配送绩效估

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

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

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

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

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

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

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

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

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

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

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

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

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

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

配送车辆路径优化问题算法研究 第4篇

配送车辆路径安排问题 (VRP—Vehicle Routing Problem) 是由Dantzig和Ramser于1959年提出的一个典型的组合优化问题, 是交通运输和物流配送领域的一个核心问题。即由多辆车将货物从一个或多个仓库送到多个地理上分散的客户, 如何安排车辆及其行驶路线使总的配送费用最小。

车辆路径问题的一般描述为:有一个中心仓库, 拥有K辆车, 容量为q, 有L个客户点, 其需求为gi (i=1, 2, ……, L) , 且gi≤q, 顶点集为V={1, 2, ……, L}, 求满足货运需求的总最短行车路线。

根据不同的约束, VRP有多种不同类型, 从上述描述中可知, 该问题是车辆数固定的单车场单车型非满载车辆路径问题。用cij表示从点i到点j的运输成本, 其含义可以是距离、费用及时间等, 设配送中心编码为0, 客户编码为1, 2, ……, L, 定义变量

建立数学模型

Xijk=0或1 i, j=1, 2, ......, L;k=1, 2, ......, K式 (6)

yik=0或1 i=1, 2, ......, L;k=1, 2, ......, K式 (7)

其中, 目标式 (1) 保证了总成本Z最小;式 (2) 为车辆的容量约束;式 (3) 保证了每个客户点的运输任务仅由一辆车来完成, 而所有的运输人物则由K辆车共同完成;式 (4) 和 (5) 保证每个客户能且只能被一辆车服务一次。

车辆路径问题流程图可以表示如下:

二、VRP问题分类

对VRP的研究重点不同, 分类方式不同: (1) 按任务持征分类:装货问题, 卸货问题, 装卸混合问题; (2) 按任务性质分类:对弧服务问题, 对点服务问题, 混合服务问题; (3) 按车辆载货状况分类:满载问题, 非满载问题; (4) 按车场数目分类:单车场问题, 多车场问题; (5) 按车辆类型分类:单车型问题, 多车型问题; (6) 按车辆对车场的所属关系分类:车辆开放问题, 车辆封闭问题; (7) 按已知信息的特征分类:有确定性VRP和不确定性VRP; (8) 按约束条件分类:带能力约束的CVRP, 带时间距离约束的DVRP和带时间窗口的VRPTW; (9) 按需求是否可切分分类:可切分的VRP, 不可切分的VRP; (10) 按优化目标数分类:单日标问题, 多目标问题。

在实际应用中VRP一般可以分为以下几类: (1) 带容量约束的车辆路径问题 (Capacitated VRP, CVRP) ; (2) 时间窗约束的VRP (VRPwith Timewindows, VRPTW) ; (3) 周期性配送的VRP (Periodic VRP, PVRP) (4) 由多个仓库向顾客提供服务的VPR (Multiple Depot VRP, MDVRP) ; (5) 开放式车辆路径问题 (Open Vehicle Routing Problem) (6) 随机需求车辆路径问题 (VRPwith Stochastic Demand, VRPSD) ; (7) 客户有物资需要回收的VRP (VRPwith Pick-Upand Delivering, VRPPD) 。

三、VRP算法研究

由于VRP对节约物流成本、提高物流系统效率有重要的意义, 该问题的求解算法一直是物流和算法研究领域的一个热点问题。目前学术界对于车辆路径问题的求解方法非常多, 但基本上可以分为精确算法和启发式算法两大类。

(一) 精确算法

常用的精确算法主要有分枝定界法、割平面法、动态规划法、网络流算法、线性搜索技术、拉格朗日分解法、列生成方法、K-树方法等。精确算法可以求解小规模VRP的最优解, 但问题规模增大时, 精确算法很难在允许的时间范围内求得满意解, 其应用范围很有限。近年来试图使用精确算法求解VRP的研究也不多。

(二) 启发式算法

采用启发式算法研究车辆路径配送问题可分为三个阶段:构造启发式算法阶段、两阶段启发式算法阶段以及智能化启发式算法阶段。

1. 构造启发式算法

构造启发式算法在求解VRP问题时通常是从初始解出发, 以邻域搜索的方式实现解的改进, 并在较短的时间内获得一个可以接受的解。代表性的主要有:

(1) 节约算法。1964年由Clarke和Wright提出, 用以解决车辆数不固定的VRP问题。该算法按节约值从大到小构造路径, 在车辆容量限制下, 求出最优路径。该算法运算速度快, 小规模优化结果与最优解很接近, 但随着规模加大, 优化结果不理想。

(2) 最邻近法。1977年由Rosenkrantz等人提出, 算法以配送中心为起始点, 搜索距中心最近的、未访问的节点作为下一个节点, 在不超出容量限制的情况下重复步骤, 达到容量限制后结束该条线路, 继续寻找其他新的线路, 直到将所有的节点都访问过。该法操作简单, 得到初始解较快, 但容易陷入局部最优。

(3) 插入法。1976年由Mole等人提出, 1983年Solomon将此方法应用于求解VRPTW问题。最近插入法的算法流程与最邻近法基本相似。用最近插入法求得的解比最邻近法求得的解更优, 但计算量耗费很大。

(4) 扫描法。它是一种逐次逼近法, 最初由Gillett和Miller提出。它假设车辆的路线位于一个几何平面上, 以起始点 (配送中心) 为原点建立极坐标系, 然后从最小角度的两个节点开始建立一个组并按逆时针方向将客户逐个加入到组中, 直到各节点需求总量超出了车辆的载重定额, 继续建立其他的组, 直到所有节点都加入到组中。扫描法求解VRP问题, 未必求得问题的最优解, 但能求得满意解。

2. 两阶段启发式算法

Christofides等于1979年提出了两阶段启发式算法, 以改进构造算法求解的不足。该算法第一阶段常用构造启发式算法来求得可行解, 第二阶段常用Insertmethod、2-exchange、2-swap、2-OPT、3-OPT等改善技术, 通过对点的调整, 向最优目标靠近, 每一步都产生新的可行解以代替原来的解, 使目标函数得以改进, 一直继续到不能再改进目标函数为止。

目前对于这类算法的研究有:Kim等建立了一个基于聚类的启发式算法, 该算法考虑了驾驶员的休息时间。首先估算所需的车辆数, 并对客户按位置聚类, 其次对每类客户使用扩展的插入算法求解。Nagy等考虑了配送和收集可并行的混合收集配送情况, 构造了一个新的启发式算法。算法通过构造路径然后使用路径反向、2-opt、3-opt和路径再插入等方法进行优化。Zhong等提出了一种称为sectionplanning的改进可行解的启发式策略, 构造了一个两阶段启发式算法。算法通过插入新路径获得可行解, 然后重新安排路径中的客户来减少路径长度。

3. 智能化启发式算法

20世纪90年代以来, 许多学者利用人工智能的优越性, 构造了基于人工智能的启发式算法 (智能化启发式算法) 。智能化启发式算法包括:

(1) 禁忌搜索算法。它是模拟人的思维的一种智能搜索算法, 即人们对已搜索的地方不会立即去搜索, 而去对其它地方进行搜索, 若没有找到, 可再搜索已去过的地方。禁忌搜索最重要的思想是:标记对应已搜索到的局部最优解的一些对象, 并在进一步的迭代搜索中尽量避开这些对象 (而不是绝对禁止循环) , 从而保证对不同的有效搜索途径的搜索。用禁忌搜索算法求解VRP问题, 虽然能保证对不同的有效搜索途径的探索, 但由于涉及复杂的邻域转换和求解策略, 在实际中不易实现。

目前使用禁忌搜索算法求解VRP的研究主要有四个方向:初始解的构造;邻域结构及邻域操作方法设计;候选集合的确定方法;构造混合禁忌搜索算法。

钟石泉等同时构造多个初始解, 设计了局部禁忌表和全局禁忌表两种禁忌表以扩大搜索邻域的范围。Brandáo使用开放初始解和K-树初始解两种方法产生初始解。符卓在当前解对应的路径内或两条路径间采用顶点重新分配、顶点交换、2-opt和“尾巴”交换的等多种邻域变换方法。钟石泉, 杜纲等又运用禁忌算法对紧急车辆调度系统进行了研究, 算法基于实数编码, 应用GENI插入法产生初始解和进行邻域操作, 设计了三种邻域, 利用容量约束控制单条路径配送点数, 采用惩罚函数处理时间窗约束, 通过设计虚拟车场等方法实现了车辆的紧急调度。

Montané等首先使用分区-路径规划方法构造启发式算法产生初始解。然后采用重新分配、交换、交叉操作和2-opt四种邻域操作, 使用前三者以及三者的组合实现路径间的结点交换, 使用2-opt实现路径优化, 以此构造了一个求解VRPPD的禁忌搜索算法。

Ho等总是选择距离最后加入路径的客户最近且满足约束的客户加入路径以产生初始解。采用结点再分配、结点分裂、结点交换和2-opt等邻域操作, 并通过不断将一条路径上的顶点加入其它路径的方法, 来减少车辆的使用 (节约路径) 。通过合并分裂顶点来减少为一个顶点服务的车辆数。以此构造了一个求解分离配送VRP算法。李松等通过车辆一任务分配结构的划分, 将大规模问题拆分成可并行计算的若干小规模问题, 提出了一种求解车辆路径问题的混合禁忌搜索算法, 可有效减少计算时间。

(2) 拟退火法。模拟退火法最初由Metropolis于1953年提出, 在80年代发展起来的一种用于求解大规模优化问题的基于热力学原理的随机搜索算法。它以优化问题求解过程与物理系统退火过程之间的相似性为基础, 利用Metropolis准则并适当地控制温度的下降过程实现模拟退火, 从而达到求解全局优化问题的目的。模拟退火算法适合大规模的需求固定或者随机需求的VRP问题。在实际应用中, 能在限制的时间内通过多次重复执行模拟退火法求出近似最优解。

单独使用模拟退火算法求解VRP的研究不多, 而主要使用模拟退火算法结合其它局部搜索算法构造混合算法。郎茂祥提出了基于客户直接排列的解的表示方法, 以此为基础给出一个求解VRPPD的模拟退火算法。算法对不可行解引入惩罚权重, 采用两交换法邻域操作和相同比率的降温策略。Tavakkoli-Moghaddam等提出一个基于最近邻域的启发式搜索算法:算法对于每一条路径, 随机产生一个未提供服务的顶点, 并将一个具有最大容量的车辆分配给该条路径, 然后搜索这个顶点的最近邻域, 并将其加入该路径, 直到容量和时间限制不再满足, 最后更新被分配车辆的容量。使用该启发式算法产生初始解, 然后使用1-opt和2-opt方法获得可行解的邻域, 以此构造一个混合模拟退火算法求解VRP。

(3) 神经网络算法。神经网络模型由Mc Culloch和Pitts于1943年提出, 模型主要是利用神经网络中神经元的协同并行计算能力来构造的优化算法。它将实际问题映射到一个神经网络上, 通过网络的动力学方程自动演化到网络的平衡态, 自动搜索到局部最优解。神经网络算法求解VRP问题规范、快速, 但可能会导致网络最终收敛于局部极小解, 另外, 参数鲁棒性较差。

王德东, 郑丕谔使用混沌神经网络算法, 对一类随机需求服从泊松分布VRP问题进行了求解, 得出该算法具有很强的避免陷入局部极小点的能力和较强的全局搜索能力。冯国莉, 杨晓冬利用Hopfield神经网络, 结合电子地图和交通路况的一些人为因素 (禁行、单行道等) , 提出了车辆行驶接近最优路径的算法和参数的学习方法。

(4) 遗传算法。遗传算法最初由John Holland于20世纪60年代首先研究。该法借鉴自然选择和自然进化的远离, 模拟生物在自然界中的进化过程所形成的一种优化求解方法。当同一级配送节点分支耗费相同, 则分别参与下一步迭代, 并由后续步骤逐渐淘汰, 最终确定最优配送路线;当同一级配送节点分支的耗费不同, 则由耗费少的配送分支继续迭代, 但还必须参与后续淘汰步骤, 直至迭代结束, 得到最优配送路线。遗传算法具有良好的鲁棒性、灵活性、通用性, 特别适合于大规模VRP问题的求解;但不能保证最大概率收敛到全局最优解。

目前使用遗传算法求解VRP的研究比较多, 研究方法主要集中在以下方面:提出新的编码方案;设计新的遗传因子;构造混合遗传算法。

邹彤就VRPTW问题提出一种基于客户的编码方案, 实现路径长度和车辆数的同时优化;贺竹磬等建立了具有时间窗约束与物流成本最小的车辆路径混合整数非线性模型, 设计了自然数插值编码的遗传算法对模型进行求解, 实现了动态交通下物流配送成本及服务水平的优化。Hwang HS设计新的遗传算子来增强遗传算法的寻优性能, 宋伟刚也通过采用一种有效的改进交叉算子, 最大程度的保留了父代的优良特性并增强了算法的寻优能力;戴树贵针对具有容量限制的车辆路径安排问题设计了带有交叉规则和选择策略的高效混合遗传算法。李彦来, 孙会君等构造了模糊模拟遗传算法, 有效的求解不确定的模糊机会约束问题, 具有良好的寻优能力。Alba E, Dorronsoro B改进了遗传算法的通用框架, 设计出了新的遗传算法。

(5) 蚁群算法。蚁群算法是Dorigo提出的一种基于群体仿生的智能优化算法, 属于元启发算法。基本思想是利用人工蚁按照人工信息素分布的概率选择下一到达的可行点, 在所有蚂蚁完成一次爬行后, 进行全局信息素的更新以反映蚂蚁搜索的效果。接着蚂蚁再次出发继续按以上规律爬行搜索直至问题收敛或出现停止条件。该算法在求解VRP问题方面有良好效果, 但存在计算时间较长、容易陷入局部最优等问题。

当前利用蚁群算法研究VRP问题主要集中在以下几方面:信息素的更新方法;下一结点的选择方法;对可行解进行局部优化以提高收敛速度。

刘志硕等针对车辆路径问题, 通过引入解“均匀度”概念来决定每次选择路径的概率以及信息素更新的策略, 引入“选择窗口”概念来确定搜索范围, 引入“吸引力”概念设计了信息素动态更新策略, 构造了一种具有自适应功能的蚁群算法。崔雪丽使用2-opt方法改进每只蚂蚁的回路, 构造了一个求解VRP的蚁群算法, 并针对特定问题讨论了相关参数的设置;Bell通过在已找到的可行解中引入2-opt等局部优化策略, 并使用候选列表 (存放离当前结点最近的结点) 指导从某个结点开始的搜索的方法, 构造了一个求解VRP的蚁群算法。于文莉将遗传算法和蚁群算法这两种算法结合起来, 对陷入局部的解进行蚁传变异, 跳出局部范围, 可以有效地求得问题的最优解或近似最优解。Reimann将大规模VRP分解成若干个子VRP, 并构造了一个分解蚁群算法。算法基于信息素矩阵引入了魅力表 (Attractivenesslist) (存放所有可行组合的期望值) , 并以此来指导从一个顶点开始的路径选择。在所有蚂蚁找到可行解尚未更新信息素时, 使用交换和2-opt优化策略改进可行解。万旭等将路径上的信息素限制在一定范围内, 只采用精英蚂蚁来更新信息素, 并对优于上代解的本代解给予激励, 对劣于上代解的本代解给予惩罚。在所有的蚂蚁已经构造完解, 但信息素还未更新之前对每代最好解采用2-opt进行局部优化。

(6) 粒子群算法。粒子群算法PSO (Particle Swarm Optimization) 是一种基于群智能方法的进化计算技术, 由Kennedy和Eberhart于1995年提出。该算法源于对鸟群捕食的行为研究。粒子群算法同遗传算法类似, 它是一种基于群体 (Populatinn) 的优化工具。系统初始化为一组随机解, 通过迭代搜寻最优值。用PSO算法求解VRP问题, 收敛速度快、依赖的经验参数少、简便易行。但也存在易于陷入局部最优的缺陷。

吴勇, 叶春明等为提高算法的收敛速度, 在每个粒子群中嵌入了记忆功能, 并对两个种群采用了两种不同的初始化方法, 提出求解带时间窗车辆路径问题的多群并行的粒子群算法。王芳设计了一种求解随机需求车辆路径问题的改进的粒子群优化 (PSO) 算法。在算法后期将变异算子引入PSO算法, 克服了基本PSO算法易陷入局部最优的缺点。

还有很多学者基于粒子群算法研究混合两种以上方法的混合粒子群算法。比如安伟刚在粒子群算法中引入了单纯形算法, 该混合算法能增强粒子群算法的局部搜索能力, 提高了算法的鲁棒性能。Russell使用分散搜索算法 (通过组合参考集中的不同解以获得更好解, 参考集中的解可以相互影响并交换信息) 求解VRPTW, 同时基于公共弧方法和最优化的集合覆盖方法, 考查了规模等参考集参数的设计。张雪东提出了基于遗传算法思想的混合粒子群算法和结合禁忌搜索的混合粒子群算法, 通过对基准测试例子的测试验证了这两种混合粒子群算法能有效的求解调度问题。

(7) 免疫算法。近年来一些学者借鉴了免疫系统的自组织学习、自适应调节的特点, 提出了用免疫算法求解VRP问题。算法中模拟了生物免疫系统对外来抗原的排除, 把抗原对应于待求解问题, 抗体对应于问题的一个解。

Prins构造了一个求解VRP的进化算法。樊建华构造了一种新的编码方式, 在减少编码长度的基础上能够提高算法的运行效率, 通过免疫记忆库的设计以及抗体之间浓度的促进和抑制机制, 可实现解的多样性, 避免收敛于局部最优解。张海刚后又采用一种改进的信息熵计算方法、交叉和变异概率的自适应机制, 构造一个改进的免疫算法来求解VSPHTW。

也有学者提出免疫克隆算法, 该法能快速收敛于全局最优解, 克服了遗传算法中易陷入局部最优解和收敛速度慢的缺点, 可有效地解决物流配送车辆路径优化问题。

四、结论

车辆路径安排对于提高物流配送效率、节约物流成本有非常重要的作用, 随着VRP规模的扩大, 精确算法研究意义不大。启发式算法, 特别是多种算法相结合的智能化启发式算法, 将是未来求解车辆路径问题的主要方法。

参考文献

[1]Kim B I, Kim S B, Sahoo S Waste collection vehicle routingproblem with time windows[J].Computers&Operations Re-search, 2006, (33) .

[2]Zhong Y J, Cole M H.A vehicle routing problem with back-hauls and time windows:a guided local search solution[J].Transportation Research, 2005, (41) .

[3]钟石泉.多车场有时间窗的多车型车辆调度及其禁忌算法研究[J].运筹学报, 2005 (, 4) .

物流配送中心作业流程的统筹优化 第5篇

物流配送中心作业流程的统筹优化

针时配送中心作业流程的.合理规划问题,对配送中心的作业时序进行分析,寻找每道工序的时差,运用统筹方法中的关键路线法寻找缩短工期的最优方案,建立线性规划模型,计算出最佳作业时序,实现配送中心内部作业优化问题,降低配送中心的运营成本.

作 者：徐慧星 XU Hui-xing  作者单位：上海铁路局金华车务段金华站,浙江,金华,321000 刊 名：物流科技 英文刊名：LOGISTICS SCI-TECH 年，卷(期)： 32(3) 分类号：U116.2 关键词：配送中心   作业时序   关键路线   工序   线性规划  

配送路径优化 第6篇

【关键词】路径优化；C-W节约启发式算法

一、引言

物流作为“第三利润的源泉”，一直是企业和社会关注的热点问题。物流配送是物流活动的重要环节，降低配送成本，提高客户服务水平，对于促进企业物流的发展具有重要的意义。物流配送运输调度即是在满足客户需求的条件下，为客户配送合理的数量，派遣最少的车辆数量并为配送车辆指派运输时间和运输费用最省的路线，即车辆路径优化问题。

二、数据获取

配送中心有3辆载重为350kg的车，车辆行驶的固定费用为305元；单位里程运输费用为1元。

各客户需求量：苏果超市汉中门大街店：33迈皋桥苏果平价店 55；苏果超市集庆路店 41；苏果奥体庐山路购物中心 33；华润苏果文靖路平价店 48；苏果超市银都店38；苏果超市银都店46；苏果超市瞻园路店 35；苏果超市（和燕路店）53；苏果社区超市（月苑社区店） 45；苏果社区超市尧林仙居店 61；苏果超市大方巷店 33；苏果锁金东路社区店 56 ；苏果超市（马标店） 36；苏果超市（后宰门店） 29

三、数学模型

公式（3-2）说明配送车辆数不能超出所拥有的车辆数；公式（3-3）该配送车辆的运量不能超过最大载重量；；公式（3-4）每个点有且只有一辆车来进行配送；公式（3-5）若点i由车辆k送货，则车辆k送完该点的货后必到达另一点j；公式（3-6）若点j由车辆k送货，则车辆k必由某点i到达点j。

四、问题求解

1.算法步骤

连接原点和其他各点，得到15条线路；根据配送中心与各客户点的距离计算节约值s（i，j）；将所有s（i，j）按其值由大到小排列；按顺序逐个考察端点i和j，若满足：点i和点j不在一条线路上；点i和点j均与基点相邻，则插入线路中。

2.节约值及结果

求解结果得到两条路径分别是：路线一：0-13-11-10-2-9-12-1-0，长度57.1km；路线二：0-4-7-3-8-14-6-15-5-0，长度62.8km。该配送中心需要2辆载重为350kg的车辆进行配送，日总费用为729.9元。

五、总结

本文对于物流配送路径优化问题进行了描述，建立了VRP车辆路径问题数学模型，并采用C-W节约算法设计某配送中心的配送路径。C -W 节约算法求解速度快、通用性强、限制条件易于加入，优先考虑一些配送中心较远的需求点是一种相当实用的启发式算法。

参考文献：

[1]黄震，罗中良，黄时慰.一种带时间窗车辆路径问题的混合蚁群算法[J]. 中山大学学报（自然科学版），2015，01：41-46.

直送式配送运输路径优化算法浅析 第7篇

1 最短路径问题

所谓最短路径问题就是指在带权有向图中，寻找从指定起点到终点的一条具有最小权值总和的路径问题。如果把权值看成是弧的长度属性(距离)，那么目标路径就是从起点到终点的最短路径，这也是其名称的由来。具体设sv和tv是网络N中的起点和终点，网络中(v i,v j)的权为wij，要找从sv到tv的通路u，使其全长为最短，即：

2 配送网络确定的直送式配送运输路径优化

所谓配送网络，简单的说是由配送中心、分散的客户以及众多交通网点所组成的网络。配送中心和分散的客户点以及各交通网点所组成的配送网络确定的情况下，我们不需要构建配送网络，直接完成搜索配送中心与客户点之间的最短路径。目前公认的解决确定网络的最短路径问题最好的方法是由E.W.Dijkstra与1959年提出来的Dijkstra算法。该算法是以网络图已经给定确定的情况为前提，设带权有向图D=(V,A)，其中V是包含n个顶点的顶点集，A是包含m条弧的弧集。

2.1 Dijkstra算法基本原理

从1v开始，给每一个顶点记一个标号，标号分T标号和P标号两种。

T标号T(v j)：表示从始点1v至vj这一点的最短路权的上界，称为临时标号。P标号P(v j)：表示从始点1v至vj这一点的最短路权，称为固定标号。

凡已得到P标号的点，则说明已求出1v到这一点的最短路径，否则标上T标号。计算的每一步都是将某一点的T标号改变为P标号，直到求出终点的P标号为止。如果v1,v 2......vn是从1v至vn的最短路径，则v1,v 2......vn-1是从1v至vn-1的最短路径。根据以上这个原理，我们得到以下的算法基本步骤。

2.2 Dijkstra算法基本步骤

开始，首先给1v标上P标号P(v1)=0，其余各点标上T标号T(v j)=+∞

(1)设vj是刚得到P标号的点，考虑所有以iv为始点的弧的终点vj，即(v i,v j)∈A，且vj的标号是T标号，则修改vj的T标号，使得：

(2)若D中没有T标号的点，则算法终止，即已求出从始点到达各点的最短路径，否则：

则把点vj的T标号修改为P标号，转入下一步。

3 配送网络不确定的直送式配送运输路径优化

配送网络不确定情况下对最短路径的搜索问题要比配送网络确定情况下困难一些。首先，我们需要构建配送中心与各客户的配送网络，然后再完成配送中心与客户间的最短路径优化。

3.1 配送网络图的构建

配送中心与客户点的相对位置是确定的，但是，它们之间还存在很多交通网络点，并且交通网络点之间可能会存在一定的连接关系。那么，在我们搜索配送中心与客户间最短路的时候，我们应该如何确定它们之间网络点的数目以及它们之间的连接关系，成为了配送网络图构建的核心问题。

3.2 构建思想

如果给定地图上全部交通网点的数目很少的时候，我们完全可以采用手工的方法就可以实现网络的构建。然而，现实中并不是这样，交通网点的数目往往特别多，手工的方法在理论上是很难实现配送网络图的构建。因此，我们必须借助计算机系统的帮助，目前运用最广的是GIS系统。

电子地图作为GIS系统的基础数据信息，通常存储了节点的位置坐标、连接关系以及相邻节点间的距离。为此，我们可以在GIS系统的支持下进行配送网络图的构建。

配送中心与客户点间网络图的构建问题核心是搜索这两点中间的其它节点，进一步根据中间节点之间的连接关系就可以构成这两点之间的网络图，如下图所示。

如果把起点S与终点T之间的网络图看作由S出发到T结束的若干个决策阶段，每个决策阶段代表一个搜索区域，其任务是选择哪些节点与上一个阶段确定的节点连接，直到T节点被选择为止。这里的S就是配送中心，T代表客户，那我们就可以借鉴动态规划思想来近似处理配送中心与客户点之间网络图的构建问题。

根据上面的思想，我们可以推导出基于动态规划思想的最短路径搜索算法。

4 基于动态规划思想的最短路径搜索算法

基于动态规划思想的最短路径搜索算法是在配送网络构建过程中直接进行最短路径搜索。算法步骤如下：

(1)确定起点S(x s,y s)与终点T(x t,y t)之间的搜索区域。矩形区域有两种类型，如下图所示：

(2)设初始搜索步长0λ=α×β(s,t)，并令i=0。其中，d(s,t)为S、T之间的搜索距离;α∈(0,1)，通常可以取为0.1或0.05;

(3)以λi=λi-1为步长进行第i阶段搜索(i=1,2,3，……)。令以λi为步长的搜索区域内的全部节点为可达状态集合，则决策规则为：当可达状态集合的某元素与G(i-1,λi-1)中的某个元素有边相连，且为弧长最小的i个节点之一时，将其记入第i阶段的允许决策集合G(i,λi)。

(4)记G(i,λi)的元素个数为k(i,λi)，进一步有如下判断规则与步长搜索规则。

新进行第i阶段搜索。重复本过程，直到为止。

如果终点T∈G(i,λi)，则搜索过程停止，转(6)。

(5)令i=i+1，转(3)。

(6)根据前后阶段节点的连接汇总G(i,λi)，根据路径长度大小确定最小路径，算法结束。

摘要：在现代物流中,配送中心的运输路径如何优化一直是热点问题。通过对直送式配送运输路径优化算法的研究,我们可以降低配送成本,提高企业运作效率,实现物流配送科学化。

关键词：直送式配送,最短路径,动态规划

参考文献

[1]邢文训,谢金星.现代优化计算方法[M].北京:清华大学出版社,2005.

[2]李维斌.公路运输组织学[M].北京:人民交通出版社,1998.

配送路径优化 第8篇

随着经济的不断发展, 商品的流通量急剧增加、市场经济一体化以及客户的订单向着多品种小批量的方向发展。面对如此复杂的环境, 配送中心发挥的作用越来越大。

配送中心内部的作业活动包括:接货、搬运、存储、拣选、分拣、出货等。拣货是指将用户所订的货品从储位中取出, 按用户分类集中、处理放置。在多品种、小批量订单的配送活动中, 人工拣选仍然是最重要的拣选方式, 人工拣选时间约占整个配送作业的30%~40%, 其成本约占总成本的90%。可见, 拣选作业的效率直接影响着配送中心的效率。

在拣选作业中, 合理进行拣选路径的优化可以有效的减少拣选的行走距离, 从而缩短拣选时间, 提高客户满意度。因此, 合理进行拣选路径的优化对于提高配送中心运作效率具有重要意义。

二.拣货路径优化问题的描述

拣货路径问题是指如何确定一个拣货单上货物的拣选顺序, 使得所有货物拣选出来时, 总的行走距离最短。拣选货物的时间是由行走时间、取货时间和等待时间组成的。Tompking的研究证明, 行走时间通常占拣选货物总的时间的一半 (如图1所示) 。由此可见, 缩短拣选行走距离对于提高拣选效率具有很大的意义。

三.拣选路径问题求解算法综述

拣选路径问题是组合优化问题, 对该类问题的求解过程比较复杂且难以解决, 已经被归属为NP难问题, 对该类问题进行研究具有十分重要的理论和实际意义。

(一) 国外研究现状

1. 传统的启发式算法在拣选路径优化中的应用。

Roodbergen和De Kostert (2001年) 以多区型普通仓库为研究对象, 对其拣选路径优化问题进行了深入的研究, 并且分别采用四种启发式算法对问题进行了求解, 并且提出了自己的“组合启发式算法”的算法, 并且通过算例证明了所设计的算法比现有的算法较优的结论。H.Hwang等 (2004年) 建立了分析模型对S型策略、返回型和中点型三种方法进行了对比研究, 指出对于小批次数量 (即订单批次数量为4) 的订单, 使用返回型策略比较好, 当订单批次数量非常大时 (即订单批次数量介于64和80之间) , S型策略最好, 处于两者之间的订单, 使用中点型策略。

在以上的文献中, H.Hwang等 (2004年) 则是以订单批次的数量为条件, 而Roodbergen (2001) 则是以多区型仓库为研究对象。

2. 混合算法在拣选路径优化中的应用。

Kees Jan Roodbergen and Renéde Koster (2001年) 将一系列的启发式算法和分支定界法应用到具有两个以上通道的仓库中, 并且比较了启发式算法和分支定界法, 并且提出了一种新的启发式算法即混合型算法, 将应用到具有两个以上仓库的拣选中, 结果表明, 该算法比现有的启发式算法都好。Osman等 (2011) 提出将订单分批和拣选路径优化结合起来, 并运用基于聚类分析的禁忌搜索算法来对拣选路径问题进行优化。

3. 智能算法在拣选路径优化问题上的应用。

国外学者运用智能算法算法来求解拣选路径的优化问题不多, 比较有典型的代表为:Khojasteh Ghamari等 (2008) 对多巷道自动化立体仓库的拣选作业问题进行了研究, 并提出了用遗传算法这一优化方法来求解拣选总时间的最小值。Seval Ene等 (2011) 首先在分类方法的基础上用整数规划的方法对货物的存储位置进行优化, 然后, 用遗传算法来来对订单的分批和拣选路径进行了优化。

以上文献, 虽然都是运用遗传算法对拣选路径问题进行的优化, 但Seval Ene (2011) 的研究则是在对货物的存储位置优化的基础上再对订单的拣选路径进行优化。

(二) 国内研究现状

1. 动态规划算法在拣选路径优化问题上的应用。

李时珍 (2003年) 提出了用动态规划的方法来优化订单拣选路径, 能有效缩短拣选的行走距离, 对于提高配送中心的效率具有重要的意义。刘亮等 (2009年) , 建立了自动仓储作业拣选路线优化问题的模型, 并应用动态规划法对建立的自动化作业拣选路线进行了求解, 得到了该模型的最优解。

在以上文献中, 李时珍 (2003) 是在传统的拣选规则的基础上, 应用动态规划的方法来建立模型;而刘亮 (2009) 则是将拣选路径问题转化为经典的旅行商 (TSP) 问题, 并利用动态规划的方法来求解该模型。

2. 混合算法在拣选路径优化问题上的应用。

杨玲等 (2011年) 利用蚁群算法结合遗传算法来求解自动化立体仓库固定货架问题, 结果表明对于待拣选货位点数目有较大范围变动的情况, 该方法能够对拣选路径进行优化, 并且在拣选的货位点数在 (10~30) , 变异概率 (0.008~0.020) 之间时是最优的。谢树新 (2010年) 并提出了基于模拟退火的粒子群算法, 来求解拣选作业的路径优化问题。

在以上文献中, 杨玲等 (2011年) 和谢树新 (2010年) 虽然都是对自动化立体仓库中的固定货架的拣选路径问题进行优化, 但杨玲 (2011年) 是将蚁群算法和遗传算法结合起来, 而谢树新 (2010年) 则是将模拟退火算法和粒子群算法相结合。

3. 智能算法。

雷娟娟 (2010年) , 研究了双区型仓库, 作者将蚁群算法与传统的拣货路径策略和S型拣货路径策略相比较, 得出了蚁群算法较优的结论。熊芳梅等 (2009年) 运用蚁群算法解决物流中心拣货路径问题, 并将其与传统的基于穿越策略的拣货路径策略相比较, 结果表明, 蚁群算法在解决拣货路径问题时在拣货路径的距离及拣货时间方面都明显的优于传统观的穿越策略。

蔺媛媛等 (2010年) , 充分结合蚁群系统、最大最小蚂蚁系统的优点, 并采用精英策略等方法, 设计出了改进蚁群算法, 将其应用到立体仓库固定货架拣选问题当中, 结果表明, 该算法极大地提高了立体仓库的使用效率。

四、结论

通过以上对配送中心拣选路径优化问题的求解算法文献的总结上, 可以看出, 在该领域的研究上存在以下几个方面的特点:

1.国外关于这一问题的研究起步较早, 国内关于这一问题的研究虽然起步较晚, 但是, 近年来国内对于这一问题的研究却明显的增多, 可见国内关于这一问题的关注度逐渐的提高。

2.无论是国内还是国外对于自动化立体仓库的拣选路径的优化研究的都比较多, 而对于人工拣选路径优化问题的研究并不多。

3.近年来, 国内学者研究运用智能算法来解决拣选路径优化问题逐渐增多, 但是却主要集中在运用智能算法来解决自动化立体仓库的拣选路径优化问题上, 将智能算法应用到人工订单拣选路径优化问题上的研究并不多。

鉴于当前很少有学者将蚁群算法应用到人工订单拣选路径优化问题上, 且在多品种、小批量的订单拣选活动中人工拣选仍然是重要的拣选方式, 为此未来加大对蚁群算法在人工订单拣选上的研究是一个重要的研究方向。

摘要：当前随着经济的发展, 配送中心发挥的作用越来越大, 而在配送中心内部的作业活动中拣选作业占据着很大的比重。本文对配送中心拣选路径问题优化算法的国内外研究现状进行了综述, 并对国内外研究现状的特点进行了总结, 并指出可以尝试将蚁群算法应用到人工订单拣选路径的优化当中, 具有一定的理论和实际意义。

关键词：配送中心,优化

参考文献

[1]Osman Kulak, Yusuf Sahin, Mustafa Egemen Taner.Joint order batching and picker routing in single and multiple-cross-aisle warehouses using cluster-based tabu search algorithms[J].Flex Serv Manuf J, 2012, (24) :52-80.

[2]Seval Ene, Nursel 0ztürk.Storage location assignment and order picking optimization in the automotive industry[J].Int J Adv Manuf Technol, 2012, pp.787-797

探析冷链物流配送路径的优化策略 第9篇

1相关概念

冷链物流作为一种极为特殊的物流供应链系统,可以将生鲜易腐产品保持在低温环境中,实现防止污染、减少货物损耗的运输目的。冷链物流共有生产、仓储、运输以及销售四个主要物流环节,这四个环节都需要在恰到好处的低温环境下进行,冷链物流是一种对运输设备与时间要求很高的特殊物流形式。冷链物流在产品、运输车辆与仓储设备、运输网络、物流公司与物流行业五个方面与常温物流存在区别。

冷链物流具有复杂性,大致可以分为四个冷冻冷藏环节:生产、仓储、运输与销售。部分特殊货物在其运输过程中需要二次预冷,冷链物流与传统常温物流二者最大的不同就是预冷与运输两个环节。预冷能够实现易腐生鲜产品长时间保鲜,可以在短时间内降低物流配送温度,使之符合产品需求,显著提升保险质量,延长物流保鲜时间。在我国当前阶段,常用的运输方式有铁路、公路、水路、航空与管道五种,调查表明,冷链物流多选择公路运输方式,在公路冷链物流中,运输车辆氛围冷藏集装箱与冷藏厢式车两种,在我国冷链物流专车一般包括保鲜汽车、冷藏汽车与保温汽车三种。

2优化策略

本文从改进遗传算法角度讨论路径优化策略。上世纪七十年代,遗传算法的概念被美国一所大学的教授在多次研究验证后提出,遗传算法(简称GA)是一种优化求解方法,其拥有自适应能力,模拟了大自然中适者生存、优胜劣汰的变异与遗传进化机制。遗传算法整体思路是在物种每一代中选取优秀遗传基因的代表性个体,父辈将优秀基因遗传,在交叉与变异后,其可以进化出更为优越的基因,更好适应环境,这一个体与其"父母"相比与最优解类似。遗传算法中,核心思想就是遗传模仿自然界中不同种群,遗传算法以模仿、交叉等方法进化各种群相关解,从中获取最优值,直至找到个体最优。其中,编码与设置初始群体的遗传操作是遗传算法的主要内容。

2.1标准步骤

遗传算法标准步骤包括七步,第一步是选择编码策略,将问题域参数转换成遗传域染色体或个体,染色体或个体由基因值排列组成,编码方法决定了染色体排列形式与选择、交叉与变异完成之后个体的解码方法(由基因型转回表现型);第二步是初始群体随机生成,初始群体随机生成许多初始解,每一数据都代表一个个体,数据整体组成初始群体;第三步是确定适应度中的取值函数,一般来说,适应度函数选择目标函数,又或者选择修正、变形后的新目标函数;第四步是确定选择概率,选择依据一定概率从初始群体选出接近最优解、环境适应能力优秀的个体遗传至下一代中;第五步是确定交叉概率,交叉操作类似大自然中的繁衍,父辈以交叉概率对两者优秀基因交换产生新一代;第六步是确定变异概率,首选需要随机选择变异个体,随后随即改变个体基因,与自然界类似,遗传算法变异概率不高;第七步是运算终止,完成遗传迭代后可以停止运算,同时输出最优解。

2.2改进步骤

在改进遗传算法解决冷链物流优化配送路径问题时,必须明确的一点是,遗传算法无法直接求解配送路线优化,其运算对象是冷链物流优化配送路径问题的解向量,这表明利用遗传算法解决问题第一步就是编码解向量。二进制编码与自然数编码在遗传算法中具有一定程度上的编码效率,在研究路径优化问题时,需要解决冷藏车辆数与运输车辆客户数量、客户服务次序这两个问题,首先确定冷藏运输车数量,其次确定运输车辆客户服务次序,再次确定客户与运输车辆的对应关系,最后得出配送方案。

遗传算法在智能式冷链物流配送运输车辆路径优化中适用范围广泛,改进遗传算法对求解广义运输成本起到积极影响,可以有效对比成本构成与广利运输成本二者的差异,具有耗时少、结果优质的特点。

结束语

总之,鉴于我国当前经济水平与人民物质生活质量逐渐提高,人民对物流服务质量的要求也随之上涨,优化冷链物流的配送路径具有十分重要的实施意义。本文从改进遗传算法角度出发对其配送路径优化策略展开探讨,在掌握相关思想理论与步骤的基础上,更好促进冷链物流优化路径,降低物流成本,提高人民生活质量。

摘要：近年来我国经济、社会不断发展,物流行业发展势头迅猛、速度飞快,冷链物流作为物流行业的重要分支之一愈发受到重视与依赖,人民物质生活水平提高与生活节奏加快使其对生鲜产品需求上涨,进一步促进冷链物流的发展。首先介绍冷链物流的相关概念,随后提出优化其配送路径的策略,以期为其更好发展做出贡献。

关键词：冷链物流,配送,路径优化

参考文献

[1]方芳.探究冷链物流配送路径优化[J].商情,2015(07).

[2]李末芝.市域连锁零售业冷链物流配送路径的优化研究[D].太原:太原理工大学,2012.

配送路径优化 第10篇

最优路径算法是GIS在路径分析中最常用的算法之一。车载导航系统、智慧交通系统等都离不开最优路径算法的应用。[1]而在快餐业配送过程中，由于行业的特殊性及配送物品的特殊性，使得其在具有一般配送的特点同时，又具有自身特点。涉及到配送路径方面的问题主要体现在以下几个方面： (1) 快餐配送对时间极为敏感。由于客户对快餐的需求都相对较急迫，且快餐本身的食物特性所带来的保温要求，使得快餐的配送要求非常迅速的将食物送达到; (2) 点餐客户位置的特殊性。如点餐客户在某个小区的某楼层内，这就要求不能将小区作为点餐点处理，而要以小区门作为关注点，考量从小区门到该客户所在楼房及楼层的距离; (3) 快餐配送受时间区段、配送工具、区域交通状况、天气状况等情况的影响。

目前传统的最优路径算法通常将路网模型理想化处理，实用性教差。较少考虑实际行驶过程中的道路属性，如道路限速、红绿灯、道路等级[2]、道路阻值、交通工具限制等。或者考虑不够全面。

2 最优路径算法优化研究

2.1 传统最优路径算法的优化

在按标记法[3]实现Dijkstra算法的过程中，核心步骤就是从未标记的点中选择一个权值最小的弧段。这是一个循环比较的过程, 如果不采用任何技巧，未标记点将以无序的形式存放在一个链表或数组中。那么要选择一个权值最小的弧段就必须把所有的点都扫描一遍，在大数据量的情况下，这无疑是一个制约计算速度的瓶颈。要解决这个问题，最有效的做法就是将这些要扫描的点按其所在边的权值进行顺序排列，这样每循环一次即可取到符合条件的点，可大大提高算法的执行效率。

2.2 在快餐配送过程中，影响最优路径算法的道路因子[1]

影响路径分析的交通影响因子很多，但是各类因子对计算结果的影响程度是各不相同的，有的只是对道路权值的影响;有的则会改变路径分析过程中路径的行进方向，可分类如下：

2.2.1 影响道路阻值的影响因子。

这类因子只会影响道路的权值属性，不会改变路径的连通性，也不会改变路径分析过程中的物体的进行方向，如红绿灯、道路等级、限速[4]、道路阻值等。这类信息可以直接在原始路网模型的基础上进行考量。

若以实际行驶速度为考量单位，下面是只考虑道路等级因素和障碍物因素的算法：[3]

V，实际行驶速度;T，选择使用的交通工具;g，经过道路的等级;d，经过道路的长度;t, N分钟商圈(N分钟商圈就是指乘坐某种交通工具，如电动车，以到达某地所需的某个具体时间为标准，这里取N分钟，所形成的一个凸包多边形);t'，行驶中遇到障碍物的等待时间(如红绿灯)。其中d值通过Dijkstra算法算出。

2.2.2 影响路网连通性的影响因子。

这类因子可直接改变原有路网模型的连通性，会改变路径分析过程中的进行方向，如单双行线、交通工具限制、斑马线天桥、道路转向等。这些因子需要将其作为路网模型的一部分然后重新建立路网模型。

2.2.3 订餐区域的影响因子。

这些因子会影响到达目前大致区域后到达顾客手上这个过程的时间，以小区为例，需要考虑的小区参数：大门口到道路的距离、小区大门口到楼宇质心点的距离，该距离可以预先分派到道路节点上、小区大门到道路的通行情况。

小区道路映射预处理过程： (a) 以小区大门为圆心，半径不断迭代增大形成缓冲区，直至与路网相交; (b) 搜索缓冲区与路网相交的道路，判断小区大门到该道路是否可达; (c) 对于可达的道路，计算其与小区大门距离，取其距离最短的连接点作为小区道路映射点。 (d) 计算的距离。

另外，为了提高系统的性能，对两两小区质心点间的路径、路径距离、通行时间，调用路网分析算法进行预先计算，结果存储在表中。

3 实际应用分析

在快餐配送的实际应用过程中，通常不单要求计算从店铺到顾客点餐地点的最优路径，还需要根据该店的辐射范围，提前计算出该店的多分钟商圈的范围，如某快餐店将自己所辐射的区域提前划分为5分钟商圈、10分钟商圈，然后可自动根据顾客来电判断处于哪个商圈范围内[5]，这样可以方便统一分配配送任务并可及时准确通知客户所需等待的时间。

N分钟商圈的算法步骤主要为：

(1)划定理想商圈范围。以该店面为圆心，以N分钟行驶距离为半径R画圆，即为理想商圈范围。公式为：R=V*T (V由选择的交通工具类别决定)。

(2)搜索映射点和nodes(道路节点)，搜索出所有的小区道路映射点和nodes。

(3)计算最优路径。遍历道路上的nodes，计算机会点到各nodes的最优路径。

i.逐个判断node到机会点的最短距离是否在N分钟行驶距离范围内;Yes则保留，No则舍弃。再根据N分钟行驶距离求出路径上的极值nodes。

ii.考虑实际行驶过程道路参数、小区参数，对nodes再次筛选。并再次计算N分钟行驶距离的极值nodes。

(4)将保留的点做最小覆盖多边形，得到N分钟商圈范围。

(5)对N分钟商圈进行修正。对于位于商圈边界附件的小区，只要小区和N分钟商圈范围相交，就将该小区包含于商圈之中。

4 结束语

本文基于最优路径算法, 设计了在快餐业配送过程中最佳送餐路径问题, 并且通过该算法的研究, 进一步利用最佳送餐路径算法应用于订餐送餐服务, 提升了快餐业的服务质量和工作效率。由于送餐路径问题是一个非常复杂的问题, 甚至行业内的不同市场定位的快餐企业所考虑的因素都不会完全相同, 所以, 本文只能结合送餐服务的通用特点, 设计了与送餐相关的影响因子, 使其与实际结合更加密切。

摘要：随着快餐业的迅速发展, 对快餐业中快餐配送问题的算法研究就愈发重要, 快餐的配送问题, 本质上就是最优路径问题, 现在分析一种最优路径算法的基础上, 结合快餐配送的诸多影响因子, 对算法进行了优化。

关键词：最优路径算法, 快餐配送,研究

参考文献

[1]魏海平, 等.顾及交通时态属性的最优路径算法与实现[J].测绘学院学报, 2004, 21 (3) :69-72.

[2]陈玉敏, 等.多级道路的最优路径算法研究[J].武汉大学学报.信息科学版, 2006, 25 (1) :70-73.

[3]吴正明, 等.基于实时交通最优路径算法的研究[J].机械与电子, 2001 (, 10) :20-22.

[4]王丰元, 等.基于交通限制的路网最优路径算法[J].交通运输工程学报, 2005, 5 (1) :92-95.

配送路径优化 第11篇

由于全球经济的迅猛发展、现代科学技术的不断更新, 物流行业作为国民经济中的重要产业, 正在全球范围内快速发展[1]。传统的货物运输产业中慢慢发展生成了一个新的分支———快递服务产业。同时随着油价上涨等一系列问题, 运输成本在物流活动中所占的比重也在不断上升, 通过合理的方法规划车辆行驶路径, 降低运输成本也成为国内各个快递企业效益提升的关键因素。

针对物流车辆行驶路径最短路问题, 国内外诸多学者对此进行了深入研究。乐阳等从网络结构的拓扑表示以及Dijkstra算法中快速搜索技术的实现入手, 提出了一种Dijkstra最短路径算法的高效率实现方法[2]。王海晓研究了Dijkstra算法在求解物流大件运输最短路径中的应用, 证明了Dijkstra算法在求解物流大件运输最短路问题的准确性[3]。黄睿分析了如何利用Dijkstra算法对物流活动进行优化, 并求得了相关物流活动的优化解[4]。潘开灵等阐述了Dijkstra算法的基本思路以及求解运输最短路径的具体步骤, 并通过Dijkstra算法找出了运输中的最短路径, 最终减少了运输距离, 降低了物流成本[5]。刘建美等研究了基于改进的Dijkstra算法的动态最短路计算方法, 并给出了相应的算例验证了算法的可行性[6]。马建刚对最短路径算法在组播路由和物流配送中的应用进行分析研究, 验证了Dijkstra算法在组播路由和物流配送问题上的有效性[7]。李擎等针对车辆最短路径规划问题提出了一种自适应遗传算法, 成功应用于车辆最短路径规划算法中, 并与Dijkstra算法进行了比较分析[8]。韩伟一针对Dijkstra算法的缺点进行了研究, 提出了一种基于Dijkstra算法的改进算法, 该改进算法解决了原来算法的局限性[9]。Heywood C等在研究基于GPS的车辆导航跟踪技术中讨论了如何利用Dijkstra算法来寻找出最短路径, 以此对装有GPS的车辆进行指挥调度[10]。Chadil N等对求解最短路问题的各种算法进行了比较分析, 同时对Dijkstra算法提出了优化改进, 证明了该改进Dijkstra算法在理论上优于其他算法[11]。Miller H等利用了Dijkstra算法求得了某企业物流配送活动过程中的最短路径, 并建立了针对该企业的物流配送数学模型[12]。Zobel D等研究了Dijkstra算法在大型运输车辆跟踪调度中的作用, 证明了Dijkstra算法可以迅速实现针对大型车辆的最短运输路径问题的求解[13]。

以上研究基本上是从寻求普通车辆最短行驶路径的单一角度出发, 并未针对我国快递配送车辆的实际情况进行研究分析, 例如没有考虑到我国快递配送车辆的载重限制等约束条件。因此, 本文将针对我国快递配送车辆运输派件过程中的实际情况, 合理设置相关约束, 并在此基础上应用Dijkstra算法来迅速准确的寻找出快递车辆配送派件活动中的最短路, 以达到帮助快递公司降低车辆运输成本的目的。

1 问题描述

相对于传统的普通运输车辆行驶路径最短路问题的求解, 我国快递车辆配送路径优化问题更为复杂, 其约束条件往往与快递配送车辆性能、货物数量、客户需求等密切相关, 即快递配送车辆与普通车辆在车辆性能要求, 服务客户需求等层面上存在差异性。因此针对实际情况, 我国快递车辆配送路径优化问题可以描述为:某国内快递公司的一辆快递配送汽车正处于公司快递配送中心所在位置, 并在此等待公司配送派件指示, 即该快递配送汽车进行配送派件活动的起始点为公司快递配送中心处。随后按照公司指示需要前往A客户所在地进行配送派件活动, 且公司快递配送中心与A客户之间存在多条行车路径, 即车辆配送派件路线的不唯一性;同时每个需要前往进行配送派件活动的客户位置和需求量一定, 并且该快递公司每辆配送派件汽车的载重量也是定值, 要求合理安排快递派送车辆的行车路线, 使该快递配送汽车的总运距最短, 并满足以下条件:

(1) 每条配送路径上所需送达给客户的快递派件总重量之和不超过该快递车辆的载重量;

(2) 每条配送路径的长度不超过快递车辆一次派件活动能够行驶的最大距离;

(3) 每个客户的需求必须满足, 且只能由一辆快递车辆进行派件;

(4) 公司快递配送中心的位置已知且唯一。

2 数学模型

通过考虑上述快递配送路径优化问题的约束条件和优化目标, 本文建立的快递车辆配送路径优化问题的数学模型如下:

设该快递公司的配送中心有K辆快递汽车, 每辆快递汽车的载重量为Ek (k=1, 2, 3, …, K) , 其一次派件活动的最大行驶距离为Lh, 需要向S个客户点派送快递, 每个客户点的快递派送量为pi (i=1, 2, 3, …, S) , 需求点i到j的运距为Uij, 配送中心到各需求点的距离为U0j (i、j=1, 2, 3, …, S) 。同时设Fk为第k辆汽车派件的客户点数 (Fk=0表示未使用第K辆汽车) , 集合Hk表示第k条路径, 其中的元素hki表示客户点hki在路径k中的顺序为i (不包括配送中心) , 设hk0=0表示配送中心, 则可建立如下快递配送路径优化问题的数学模型

约束:

上述模型中:

式 (1) 为目标函数;

式 (2) 保证每条派送路径的长度不超过快递汽车一次能够派送的最大行驶距离;

式 (3) 保证每条路径上各客户点所需快递派送量之和不超过每辆快递车辆的载重量;

式 (4) 表明每条路径上的客户点数不超过总客户点数;

式 (5) 表明每个客户点都得到派送快递服务;

式 (6) 为每条路径的客户点的组成;

式 (7) 限制每个客户点仅能由一辆快递汽车进行派件活动;

式 (8) 为当第k辆快递汽车服务的客户数≥1时, 说明该快递车辆参加了派件活动, 则取sign (Fk) =1;当第k辆快递汽车服务的客户数<l时, 表示未使用该汽车, 因此取sign (Fk) =0。

3 Dijkstra算法

3.1 Dijkstra算法介绍

Dijkstra算法由荷兰算法学家Edgar Wybe Dijkstra在1959年首次提出。该算法是一种典型的最短路算法, 一般用于解决有向图中单个源点到其他各个端点的最短路径问题。在现实生活工作中, 许多问题都与寻找一个图的最短路径问题密切相关, 比如交通路线的选择、城市下水管道的布局、网络线路的铺设等问题。50年代末, Dijkstra提出了按路径长度不减次序产生的最短路径算法。Dijkstra算法按照从给定起点到图中顶点的距离、顺序求出最短路径。Dijkstra算法的主要特点可以概括为以起始点为中心向外层层扩展, 直到扩展到所需解决问题的终点为止。

与此同时, 目前在求解物流配送车辆最短行驶路径问题上应用的较为广泛的算法还有遗传算法, 蚁群算法以及A*算法。这四种算法求解该类问题时所得的结果不仅准确度高, 且计算耗时少, 因此这四种算法在求解相同问题时具有一定的可比性。

3.2 Dijkstra算法流程

Dijkstra算法的基本思路是将快递车辆配送最短路径问题所描述的路径网络图中的每个节点都赋予一个标号 (an, bn) , 其中, 路径网络图中的每个节点代表了快递公司的各个不同客户所在位置或者快递公司自身配送中心所在处。从起点s到节点n的快递车辆最短配送路径长度将被记作an, 从起点s到节点n的最短快递配送路径中n点的前一点会被记为bn, 一个节点到其自身的最短路径长度设为0, 若两节点之间不存在车辆行驶路径, 则其距离设为inf (即无穷大) 。

Dijkstra算法寻求从起点s到点n的快递车辆最短配送路径基本过程如下:

(1) 初始化, 起始点设置:

第一步:设as=0, bs为空;

第二步:设所有其它结点:at=∞, 针对不同的目标点寻找最短路径时, bt则不同;

第三步:首先标记起点s, 并记l=s, 其它所有点均设置为未标记的。

在此注意, 起始点既可以为快递公司自身配送中心所在处, 同时也可以为快递公司某一客户所在位置。

(2) 计算检查从所有已标记的快递公司客户节点l到其直接连接的未标记的其他客户节点n的距离, 并设置如下:an=min{an, al+hln}

式中, hln为节点l到n的直接连接距离。

(3) 选取下一个客户结点, 从所有还未标记的结点中, 选取an中最小的一个i值:ai=min{an, 所有未标记的点n}

找出i在该快递车辆配送路径网络图中所对应的客户节点, 并将其设为已标记的。

(4) 寻找出点i的前一点, 从已标记的点中寻找出直接连接点i的点z作为前一点, 并设i=z。

(5) 标记点i, 此时如果所有点均已标记, 则算法退出并得到快递车辆配送最短路径, 否则记l=i, 转到步骤 (2) 再继续重复上述流程。

由上可得, 如果该快递车辆配送路径网络图中客户节点数越多, 则相应的算法循环次数越多, 因此将会使计算时间稍微延长。Dijkstra算法所采用的图遍历是以快递公司客户节点数作为基数来进行二次循环, 每重循环的次数均等于客户节点数q, 它的执行过程会产生以s为顶点的一棵树, 同时伴随着算法的进一步执行该树会向四面八方延伸, 直至最后到达终点为止, 其算法执行的时间复杂度为O (q2) , 通过该算法可以准确的在快递车辆配送路径网络图中寻找出从起始点s到其他所有节点的最短路径。综上所述, Dijkstra算法的基本流程如图1所示。

4 案例分析

根据收集到的资料, 国内一家快递公司在上海张江高新科技园区的某片区拥有20个客户, 该公司的快递车辆经常需要在这20个客户之间进行收发派件的物流活动。根据资料, 某次此快递公司的车辆b在该片区进行快递收发配送时正处于客户2位置处, 现根据客户要求需尽快前往客户20所在地进行收发派件。因此该快递公司的车辆监控调度部门需要尽快寻找出从客户2到客户20之间的最短路径并及时告知车辆b司机, 所以如何迅速准确的寻找出从客户2到客户20的最短路便成为这次车辆调度能否成功的关键所在。同时根据公司平时记录的数据, 目前在未使用Dijkstra算法进行路径优化的情况下, 快递车辆b从客户2到客户20平均需行驶54.2321km, 平均耗时60分钟。

综上所述, 本文选择了目前在算法编程实现上应用较为广泛的Matlab软件来进行该最短路问题的Dijkstra算法编程求解。因为在Matlab中进行Dijkstra算法的编程求解时需要知道各个节点的位置坐标, 所以综合收集到的资料以及考虑Dijkstra算法的编程过程, 该片区20个客户点的位置分布需要根据Matlab的程序规则进行转化, 其转化为X, Y平面的位置坐标如表1所示。

同时从收集到的资料分析得知, 该企业快递派送车辆一次派件活动的最大行驶距离Lh=50km, 车辆的载重量Ek=8×103kg, 且本次客户点20的派送需求量p20小于Ek, 需求点2到20的运距为U2 (20) 。

通过学习上文3.2节提到的Dijkstra算法流程, 本文在Matlab中对上述最短路问题按照该算法思路进行了编程实现。首先在程序中设置了节点2作为起点s, 终点n设置为节点20;其次在程序中建立了一个距离矩阵, 保证了各节点之间路径的存在性;最后在程序中编入了相应参数, 最终该代码运行后得到的求解结果在Matlab命令窗口显示如下:

Start id=2;

Finish id=20;

Distance=40.3565;

Path=[2 16 12 11 20];

Computing time=4;

即通过该算法在Matlab中的编程实现结果可以得知起始点s是客户2所在地, 终点n是客户20所在地, 这两个客户之间的最短路径a20=40.3565km, 且最短路径分别经过客户2、16、12、11、20, 同时Dijkstra算法求解该最短路问题的求解时间为4秒。

本文同时在Matlab中针对上述最短路问题也分别根据遗传算法, 蚁群算法和A*算法的求解思路进行了编程实现。这三种算法代码运行后得到的求解结果在命令窗口分别显示如下:

遗传算法求解结果:

Start id=2;

Finish id=20;

Distance=40.3565;

Path=[2 16 12 11 20];

Computing time=5;

蚁群算法求解结果:

Start id=2;

Finish id=20;

Distance=40.3565;

Path=[2 16 12 11 20];

Computing time=6;

A*算法求解结果:

Start id=2;

Finish id=20;

Distance=40.3565;

Path=[2 16 12 11 20];

Computing time=8;

由以上算法运行结果可以看出, 这几种算法针对上述最短路问题求出的最优路径相同, 而在算法运算时间上存在差异性, 如表2所示。

由表2可以得出, 针对该快递车辆配送路径优化问题, 在求得相同最短快递配送路径的情况下, Dijkstra算法的计算时间最短, 仅为4秒, 明显优于其他3种算法。同时该Dijkstra算法代码运行后得到的图像结果在Matlab的图表窗口显示如图3。

图中黑线代表了各节点之间存在的行驶路径, 蓝色数字分别代表了该节点的客户编号, 且在程序中设定了X轴为图中的横轴, Y轴为图中的竖轴。程序按照Dijkstra算法的流程运行后便迅速的寻找出了从客户2到客户20之间的最短路径并对其进行了标记, 即图中的红点和红色线条所示。同时经过验证, 该路径正是从客户2到客户20之间的最短路径, 且根据车辆b反馈的结果可知, 行驶40.3565km的平均耗时仅为42分钟。优化前后结果对比如表3所示。

综合分析优化前后结果可得, 车辆b需要按照从客户点2———16———12———11———20的路径行驶, 这样才能确保车辆b是沿着最短路径到达客户20所在处进行派件, 并且该次派件的最短运距U2 (20) 仅为40.3565km, 既低于优化前的54.2321km, 又满足该企业快递车辆每次派件的最大行驶距离需小于50km的条件, 同时优化后车辆b从客户2到客户20的平均耗时也从60分钟降低为42分钟, 综上可知通过运用Dijkstra算法可以迅速有效的寻找出车辆快递配送的最短路径, 从而极大地降低车辆派件的运输成本。

5 总结