物流配送路径优化策略研究

2023-04-01 来源：画鸵萌宠网

第29卷　第5期2005年10月

武汉理工大学学报(交通科学与工程版)

JournalofWuhanUniversityofTechnology

(TransportationScience&Engineering)

Vol.29　No.5Oct.2005

物流配送路径优化策略研究

周　程

(湖北经济学院工商管理学院　武汉　430205)

摘要:配送是物流中的核心环节,最短路径的选择决定着配送效率.从图论的角度出发,分析了经典的Dijkstar算法和Floyd算法,并指出了它们的一些不足:Dijkstar算法随着配送点数目的增多,效率将下降;Floyd算法主要解决有向图等.给出了一些改进的建议:针对Dijkstar算法,将交通路线图分成子图,以提高效率;对于Floyd算法,将邻接矩阵上三角和下三角复制,能解决采用Floyd算法解决无向图的最短路径问题.针对某物流配送公司,给出了基于改动后的Floyd算法的程序实现,开发了一个配送路径优化决策系统.

关键词:物流;配送;最优路径;Dijkstar算法;Floyd算法中图法分类号:U492222

0　引　　言

随着现代社会的发展,物流、商流和资金流广泛深入影响着人们的日常生活.电子商务主要是基于互联网络的虚拟经济,而物流促使电子商务由虚转化为实.物流系统是现代社会经济系统的支柱.关键的物流活动包括:仓储、物料搬运、包装、运输等,其中配送运输是最大的物流成本之一,因此配送运输活动组织得好坏,直接影响着物流活动的成败.配送运输是指将被订购的货物用汽车或者其他运输工具从供应点送至顾客手中的活动,其间可能是从工厂等生产地仓库直接送至客户,也可能通过批发商、经销商或由配送中心、物流中心送至客户手中.配送运输[1]通常是一种短距离、小批量、高频率的运输形式.配送的目标之一就是以最小的代价,将产品从原产地(或物流配送中心)转移到规定地点.因此,对制定车辆调配计划和配送路线计划就显得非常重要了.通常,最小的代价所对应的配送路径就是最优路径.文中首先介绍在物流行业中配送问题的分类和常用路径选优算法,重点分析对比了Dijkstra算法和Floyd算法,结合Floyd算法给出一种简单易行的

1　配送问题的描述

物流行业中配送优化策略研究的主要内容就是配送车辆优化调度.在物流配送过程中,影响配送运输效果的因素主要分成两种:一是动态因素,如车流量的变化、道路施工、配送客户的变动、可供调动的车辆变动等;二是静态因素,如配送客户的分布区域、道路交通网络、车辆运行限制等.各种因素相互影响,很容易造成送货不及时、配送路线选择不当.配送问题面临的一个核心难题就是求解最短路径.最短路径问题一般可分成三类:一是距离上的最优;二是经济上的最优;三是时间上的最优.

配送问题抽象如下:设有一物流企业需要向n个配送节点配送不等的货物Qi,已知每个节点路径各自对应的权值,求最优的配送车辆搭配和各自路线最优规划,即使在相应约束条件下(如时间范围内或一次到货等),配送系统的总权值最小.本文对这个问题采用图的结构进行描述:图的顶点表示配送中心和配送点,边表示它们之间的线路联系,边赋予相应的权值(表示时间、距离、线路运况等),这样配送问题就转化为在网络图求解路线的权值最优,权值可代表距离、时间、费用或它

配送优化策略,最后给出程序运行结果.

　　　　收稿日期:20050514

　　　　周　程:女,27岁,硕士生,主要研究领域为物流管理

・798・武汉理工大学学报(交通科学与工程版)2005年　第29卷

们之间的综合因子,配送优化问题就要求在从始点到终点的所有路径中找出一条总权数为最小的路径[2,3].

D[i]=arcs[LocateVex(G,V)[i]󰃜vi∈V].

Step2　选择Vj,使得D[j]=min{D[i]󰃜Vi∈

V-S}.Vj就是当前求得的一条从V出发的最短

2　Dijkstra算法及分析

首先讨论求解单源点的最短路径问题:给定带权值有向图G和源点V,求V到图中其余顶点的最短路径.如图1所示的带权有向图G5中从V0到其余各个顶点之间的最短路径如表1所列.

路径的终点.令S=S∪{j}.

Step3　修改从V出发到集合V-S上任意一顶点Vk可达到的最短路径长度.如果D[j]+arcs[j][k]Step4　重复Step2和Step3就可求得V到图上其余各个顶点的最短路径.

　　Dijkstar算法思路清晰,程序实现简单.但是Dijkstar算法存在三重循环,第一重循环时间复杂度为O(n),第二和第三重循环为嵌套循环,时间复杂度为O(n2).因此求解一顶点到另一顶点的最短路径时,采用Dijkstar算法的时间复杂度为

O(n).当顶点n较大时,算法的时间复杂度急剧增加,即使用带权的邻接表作为有向图的存储结构,则修改D的时间可以减少,但由于在D向量中选择最小分量的时间不变,所以总的时间复杂度仍然为O(n2).这里介绍一种改进策略,主要思想是将整个带权值有向图分区划分成各个子图,这也和现代物流配送企业分区配送一致,这样人们只需要对各子图进行划分计算各自顶点的最短路径,最后将其综合决策进行处理.划分的基本原则如下:两点之间直线距离为最短几何距离,因此一般最短路径在配送起点和终点连接的直线周围.因此应该沿着连接起点和终点的直线进行划分.同时,系统还应该开辟存储结构,将已经计算好的顶点之间最短路径存储在数据库中,避免进行重复性工作.

图1　带权有向图G5

表1　有向图G5中从V0到其他顶点的最短路径始点

VVV0000终点

VVVV1234最短路径(V0,V1)(V0,V1,V2)(V0,V3)(V0,V4)路径长度

15302520　　从图1中可看出从起始点V0到顶点V2有两条路径(V0,V3,V2)和(V0,V1,V2),路径(V0,V3,V2)长度为35,路径(V0,V1,V2)长度为30,显然路径(V0,V1,V2)是V0到V2的最短路径.Dijkstar提出了一个按路径长度递增的次序产生最短路径的算法.首先引入一个中间辅助变量D[i]表示当前源点V到每个终点Vi的最短路径的长度.D[i]的初始值为:如果源点V到终点Vi之间有直接相连的路径,则D[i]为这条路径的权值,否则,设定

D[i]=MAX.设

D[j]=min{D[i]󰃜Vi∈V}

3　Floyd算法及实现

针对求解交通网络中的任意顶点之间的最短路径时,Dijkstar算法主要是求解单源点的最短路径问题.这里以每个顶点作为源点,重复运行Dijkstar算法求解,就可获得每对顶点之间的最短路径,总的时间复杂度为O(n3).下面引入Floyd算法求解每对顶点之间的最短路径,并给出一种简单实现的基于Floyd算法的求解最短路径的系统.Floyd算法仍然从带有权有向图的邻接矩阵出发求解最短路径的,经典Floyd算法描述[4,7]如下.

假设求解从顶点Vi到顶点Vj的最短路径.如果从Vi到Vj有弧,则从Vi到Vj存在一条长度为

　　显然D[j]为从源点V出发的一条最短路径,下一条最短路径的长度一定是

D[j]=min{D[i]󰃜Vi∈V-S}其中:S为已经求得最短路径的终点集合.经典

[4～6]

如下.Dijkstar算法描述

.假设采用带权的邻接Step1　系统初始化

矩阵arcs表示带权有向图,arcs[i][j]表示弧

上的权值.若顶点Vi和顶点Vj不直接相连,则arcs[i][j]给定MAX(极大值).S为已经找到从V出发的最短路径的终点的集合,它的初始状态为空集.那么,从V出发到图上其余各顶点(终点)Vi可能达到的最短路径长度的初值为

　第5期

周　程:物流配送路径优化策略研究

NextjNextiNextkEndFunction

・799・

arcs[i][j]的路径,该路径不一定是最短路径,尚

需要进行n次试探.首先考虑路径(Vi,V0,Vj)是否存在(即判断弧(Vi,V0)和(V0,Vj)是否存在).如果存在,则比较(Vi,Vj)和(Vi,V0,Vj)的路径长度取短者为从Vi到Vj的中间顶点的序号不大于0的最短路径.假如在路径上再增加一个顶点V1,也就是说,如果(Vi,…,V1)和(V1,…,Vj)分别是当前找到的中间顶点的序号不大于1的最短路径.将它和已经能够获得的从Vi到Vj中间顶点序号不大于0的最短路径相比较,从中选择中间顶点的序号不大于1的最短路径之后,再次增加一个顶点V2,继续试探.依次类推.在一般情况下,若(Vi,…,Vk)和(Vk,…,Vj)分别是从顶点Vi到顶点Vk和从顶点Vk到顶点Vj的中间顶点的序号不大于k-1的最短路径,则将(Vi,…,Vk,…,Vj)和已经得到的从Vi到Vj且中间顶点序号不大于

k-1的最短路径相比较,其长度最短者便是从V

针对华中地区某物流公司配送方面存在着下列问题:车辆运输线路优化不合理,主要实行单车配送,车辆经常不能够满载,运力浪费严重,没有实行协同送货等问题.结合将邻接矩阵上三角和下三角权值复制改进的Floyd开发一个中小物流企业配送系统.配送系统整体框架如图2所示.

图2　配送系统功能模块

到Vj的中间顶点序号不大于k的最短路径.这样,在经历n次比较后,最后求得Vi到Vj的最短路径,按照相同的方法可获取所有顶点相互间的最短路径.

显然经典的Floyd算法主要针对带权有向图而言,对于无向图,它并没有考虑,其实只需要稍微改进就可以实用于无向图,采取的策略为将邻接矩阵上三角和下三角复制,从而每条边就成为双通的路径,采用原Floyd算法就可求解任意顶点间的最短路径.Floyd算法的程序如下.

PrivateFunctionFloyd(beginAsInteger)　Fori=0Tobegin　Forj=0Tobegin

Ifi<>jThen

a(i,j)=graph(i,j)

Else

a(i,j)=0

EndIf

Ifi<>jAnda(i,j)Else

pat(i,j)=0EndIfNextj　Nexti

Fork=0Tobegin

Fori=0TobeginForj=0Tobegin

Ifa(i,k)+a(k,j)EndIf

从企业运行成本的角度设想,站点录入机制采用模拟的电子地图而没有采用地理信息系统,将与企业有业务往来的配送点通过录入界面录入并存储于数据库中.站点录入界面主要是生成各个配送点在模拟电子地图上的具体坐标,即标定各个配送点的位置,而站站录入界面主要是生成每个配送点及配送中心之间的路径关联,也给定相应的权值.采用Floyd算法可获得任意顶点之间的最短路径线路.显然系统将录入的电子地图上任意顶点之间的最短路径都存储在数据库中,这样就避免了重复性的工作,提高了系统效率.

给出一个配送任务:从配送中心0送1单位的货物到配送点6,送2单位货物到5,送1单位货物到4,送0.5单位货物到3,选择载重量为4.5单位的车辆,配送系统运行主界面如图3所示.车辆调度策略是需要一辆载重为4.5t的车完成配送任务,最优行车路线为(0,12,6,5,4,3,0).

图3　配送系统运行界面

・800・

参考文献

武汉理工大学学报(交通科学与工程版)2005年　第29卷

4　朱永升,韩伯棠,夏　平.交通限制条件下城市物流配

送路线优化选择.武汉理工大学学报(交通科学与工程版),2004,28(3):391～394

5　孙毅彪,王程铭.基于有向图规划的最佳物流路径策

1　苏一丹,李　桂.电子商务物流管理信息系统中最优

(佳)径算法的研究.计算机工程与应用,2002(18):182～183

2　李腊元,李春林.计算机网络技术.第2版.北京:国防

略分析及应用.运筹与管理,2003,12(2):110～113

6　黄伟东,万义玲.公路网最佳路径算法的研究.南昌大

工业出版社,2004.185～190

3　李春林.QoS多播路由技术进展.武汉理工大学学报

(交通科学与工程版),2001,25(4):386～389

学学报(工科版),2001,23(1):48～52

7　周炳生.Floyd算法的一个通用程序及在图论中的应用.杭州应用工程技术学院学报,1999,11(3):1～9

ResearchonOptimizeMethodofLogisticsDeliveryRoute

ZhouCheng(SchoolofBusinessAdministration,HubeiUniversityofEconomics,Whhan430205)

Abstract

Sincethedeliveryisthekeypointoflogistics,shortestpathdecisionisessentialfortheefficiency

ofdelivery.ClassicalDijkstaralgorithmandFloydalgorithmareanalyzedfromthepointofviewofGraphTheory.Itpointsoutthesetwoalgorithmsdeficienciessuchas:Dijkstaralgorithmefficiencywilldropfastwiththenumberofdeliverypointincreasing,Floydalgorithmmainlysolvesthedirectiongraphproblemandnotfitfornon2directiongraphproblem.Thensomeimprovementmethodsarebroughtforwardsuchas:forDijkstaralgorithm,thewholegraphisdividedintosomechildgraphandthenitwillincreasetheefficiency,forFloydalgorithm,theabutmatrixismodifiedtoanequalmatrixandthenitsolvesnon2directiongraphproblembasedonFloydalgorithm.Finally,anexampleoflogisticsdeliveryrouteoptimizationbasedonFloydalgorithmisgiven.Keywords:logistics;delivery;optimizationmethod;dijkstaralgorithm;floydalgorithm

(上接第787页)

ResearchonConcreteAppearanceDefectExtractionandRecognitionBasedonMatrixPrincipalComponentsAnalysis

ChenXiaojia　ZhouXiangjun　LiYicheng(SchoolofTransportation,WUT,Wuhan430063)

Abstract

Thispaperdiscussesanewmethod,whichcanrealizetoinspectdefectsandrecognizevariousdefecttypesonconcretesurfacebytechniqueofdigitalimageprocessingandpatternrecognition.Thepaperemphasizesonresearchoffeatureextractionandneuralnetworksclassifierdesign,whichmusthavecredibilityandavailabilitytomeettheneed.Thematrixprincipalcomponentsanalysis(MATPCA)method,whichisaneffectivemethodofanalyzingdatainstatistics,iswidelyusedinthedatafeatureextractionanddatacompressionforhigherdimensionaldataspacecanbetransformedintolowerdimensionalfeaturespacebyMATPCAmethod.Inthispaper,theimagepixelfeatureextractedbyMATPCAmethod,whichisrealizedbythetoolofMATLAB,canmeettheneedtherecognition

.Intherecognitionlayer,theBPneuralnetworkmethodisdiscussed.Therecognitionlayerwell

resultsshowthatitiseffective.

Keywords:matrixprincipalcomponentsanalysis;featureextraction;concrete;externalappearance;

neuralnetwork

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文

全部栏目

物流配送路径优化策略研究