基于Dijkstra算法在物流配送中的应用

SFW R EE0M N N EI 0r A E VLP ET DDS N D A G

软件开发与设计

基于 Djs a i t算法在物流配送中的应用 kr凡金伟。吕康(. 1郑州商业贸易技师学院，郑州 4 0 6;2河南教育学院，郑州 4 04 ) 506 . 5 0 6摘要：本文研究了我国电子商务环境下物流配送存在的问题，提出了改进对策。关于物流路径的选择有很多方

法，本文将 Djs a i t算法引入到物流配送，达到了费用最小的目的，提高了工作效率，因此该方法合理有效。 kr关键词：物流配送； i s a算法； Dj t kr最短路径

S d nt i s a l r m A p ct oii ir u o t y e j t g i pl a d nLg t s s i t n u o h D k r A ot h i ei sc D tb iF iw i L AN Jn e U,( . e g h uCo 1 Zh n z o mmeca a eT c nca n tue Z e g h u4 0 6; . n n Is tt fE u ain Z e g h u 4 0 4 ) ril d e h iin Isi t, h n Z o 5 0 6 2He a ntu eo d c t, h n Z o 5 0 6 Tr t i oAb t a t Thsp p rs d e e p o l mso gsi sd s b t n i u - o sr c: i a e t ist r b e f o it it u i n o re c mme c n i n n, u o w r o n eme— u h l c i r o r e e v r me t p t r a d c u t r a o f

srs oipoe T eeaealt f as b u l iis ir ui hoe T iat l i rd c i saa o tm io ue rv. h r r y oto sc s b t nt c os. hs rc t ut Dj t l rh t t m o ow a gt d t i o o ie n o s k r gi nl gsisd sr u in I h ss r e e e p n e s l s up s, as d t e w r i ge f in y t ee o e t i meh d r a o— o i c it b t . t a e v d t x e s ma l t r o e r ie o k n f ce c, rf r h s t i o h e p h i h to e s na e e ecie bl f

tv .

Ke r s o i i i r ui; i s aA gr h; h r s P h ywo d:L gs c D s i t n Dj t lo tm S ot t a h t s tb o k r i e

l引言 电子商务是依托于互联网和信息技术的一种新型商务活动。目前，我国的电子商务发展势头迅猛，已经成为国民经济中的重要组成部分。

源节流，降低物流成本和配送服务的价格，同时还应尽可能与电子商务公司建立长期稳定的协作关系，这样做有利于物流企业制定长远投资和服务计划，有利于加快新的物流配送

技术的应用，加大配送渠道和设施的建设力度，最终有利于加快实现物流配送系统的信息化、自动化、网络化和智能化。 从长远看，有利于持续稳定地降低物流配送的成本和价格。 目前关于物流配送的问题已经有很多方法，大致可分为定性和定量两大类。定性方法是指凭借个人或集体的经验来做出决策，它的执行步骤一般是先根据经验确定评价指标， 对各待选中心利用评价指标进行优劣性检验，根据检验结果

相对于新生的电子商务来说，物流配送出现得比较早但是真正把它当作一个完整的系统来研究还是在 2 O世纪 5 0年代

初。在电子商务尤其是 B C业务开展之初，国内还没有一家物 2流公司具有电子商务的配送经验，各个电子商务公司只能求助于具有国内最大覆盖网络的中国邮政速递公司 E,但是在经 MS历一段时间之后，E S由于自身体制的僵化分割，管理无法协 M

调、服务水平无法提高、费用居高不下，对很多问题都是心有余而力不足，无法满足电子商务发展的快速要求。鉴于此种情景，国内的许多大型电子商务公司都在积极地寻找出路，有的自己投资组建配送队伍，但是要将自己的

作出决策。定性方法的优点是注重历史经验、简单易行，其缺点是容易犯经验主义和主观主义的错误，并且当可选地点

较多时不易做出理想的决策。定量方法根据各种约束条件和所要达到的目标，把选址问题转化为函数，再利用合适的算法进行求解，求出最符合条件的解 (即具体的地点)作为配送路径。本文给出一种基于最短距离改进问题的算法的物流配送路径方法。

网点覆盖全国实在太难、投资太

大；有的积极寻找新近进入电子商务配送领域的配送公司，但是后来者的实力和发展速度着实无法满足需求；也有求助传统的第三方物流公司，在电子商务覆盖需求如此广大，服务环节如此复杂，业务特点往往品种多、数量少、利润低等实际问题面前，传统的物流

2最短路径法 采用图论中的最短路径算法来建立物流配送路径选择模

公司往往是望而却步。 商品配送成本过高。电子商务公司的配送不仅面向批发

型。它的主要思想是从代表两个顶点的距离的权矩阵开始， 每次插入一个顶点比较任意两点间的已知最短路径和插入顶点作为中问顶点时可能产生的路径距离，然后取较小值以得到新的距离权矩阵。当所有的顶点均作为顶点时，得到的最后的权矩阵就反映了所有顶点间的最短距离信息。最短距离者作为费用最小者，即最佳的选址位置。由于最短路径问题有着广泛的应用背景，国内外大量专

商和零售商，还要直接面对大批的最终消费者，况且电子商务不受时间、地域的限制，因此较难形成集中的、有规模的配送流量，由此造成配送任务复杂而琐碎，成本居高不下。

降低配送服务价格，就要解决电子商务公司与物流配送企业之间在配送服务价格之间的矛盾，需要双方的共同努力。一

方面电子商务公司考虑配送成本，尽量将网上销售的商品

家学者都对此问题进行了深入的研究。经典的图论与不断完

控制在与物流企业协议确定的配送范围之内，并尽量使之相对集中且形成规模。另一方面，物流配送企业应积极协作， 选择最短路径作为配送路径降低配送成本，并加强管理，开本文收稿日期：20 0 8年 1 2 O月 5日

善的计算机数据结构及算法的有效结合，使得新的最短路径算法不断涌现。据统计，目前提出的此类最短路径的算法大约有 1 7种。F B na i Z a . ejmn h n等人对其中的 l 5种进行了测试，结果显示有 3种效果比较好，它们分别是：Q ( ah T Q g p r1— 9—

—

—

电脑编程技巧与维护go twt toq e e) K ( eteDjs a Sagrh rwh i uu s、D A t i t loi m i hw h h kr t m—

图 1为系统工作流程

图，主要实现步骤如下：

pe etdwt apoi t b ces l ne i p rx e u k t m h ma )以及 D D fh i s a K eDj t’S t kr

a oi mipe n d i o beb ces。其中 T Q算法的基 l rh m l t wt du l u kt g t me e h ) Q础是图增长论，用两个 FF IO队列实现了一个双端队列结构来

支持搜索过程，较适合于计算单源点到其他所有点的最短距离。后两种算法则是基于 Djs a i t算法，采用桶结构明显提高 kr了永久标记点的搜索速度。

两 篙 鏖图 l系统工作流程图

[ 1

3算法原理及应用 Djs a i t算法是由荷兰计算机科学家艾兹格 kr迪科斯彻提出的，可用来找出图中指定节点到其他节点间的最短距离。其 主要思想是首先从源点求出长度最短的一条路径，然后通过

()抽象城市道路为网络图。首先对城市道路进行编辑 1处理，使其与实际道路相符合，并进行拓扑检查，生成线与线相互交叉的道路图；然后创建城市道路拓扑，拓扑关系构建了相邻弧段和结点之间的关系；最后生成道路网络拓扑文 件，文件中定义了共属性特征如弧段的起始节点、终止节点， 弧段长度等，为最短路径计算准备数据。

对路径长度迭代得到从源点到其他各目标节点的最短路径。具体求解过程如下：

设 w是从源点 S j到节点 j的最短路径长度；p是从 S j J到

的最短路径中 i的前一节点。s是标识集合；T是未标识集点合；M是节点集合。d是节点 i i j到节点 j的距离 (与 j i直接相连，否则=。 ) () S{ T M—;j s (E,与 j接相连 )或 w= 1= S= S=; jTs l; w d 直 j。 i T S j直接相连)。(,与不 。

()最短路径求解。首先读取城市道路网络图；然后系 2统根据屏幕输入坐标，寻找道路网中的最近点作为最短路径分析的起点和终点，利用 Djs a法计算满足条件的弧段， i t算 kr 并依顺序连接所有弧段；最后裁剪起终点两端的多余部分，返回最短路径。

()在 T中找到节点 i 2,使 S i到的距离最小，并将 i划归到S (可从与 s直接

相连的 J中考虑)。若 d= id j￣mn ( ,j与S接相连，则将 i归到 S中，即 S{ i,T 1 l;p s直划： S} -’ i i。, - l=

()最短路径显示与漫游。S yi 3 k l e中通过程序接口读取 n计算结果，并在三维场景中进行显示和设定为路径，系统提供模型角色沿路径进行漫游浏览。42数据存储结构设计 .

()修改 T中 j 3节点的 w值：jr n(j idj 0∈∈ j w= i w,+ i a w ) TiS若州值改变，则 p l ); j‘=。

Ac I rG S是 E R公司开发的一套完整的 G S用产品，它 SI I应通过对地理现象、事件及其关系进行可视化表达，构建特定 的应用，提升工作效率。系统通过它进行城市道路的拓扑创建工作，并生成拓扑文件，把城市道路网抽象为关系图。系统借助 A c I开发引擎 A c nie快速访问道路拓扑图， rG S的 rE gn

()选定所有的 w最小值，并将其划归到 s中： 4 i这样就得到一个与供应商、工厂及用户间的最短距离， 在费用、时间等方面的花费也相对要小得多，故可以将该物流中心选在该点处。

w= n j0∈;= L i;=~{若 Iln。 w s s J( T T i mi i l}; S=,所有节点已标识，则算法终止，否则，转入步骤 () 3。 Djs a i t算法通用性强，既可以解决单源点间的最短路径 kr问题，也可解决所有点对之间的最短路径问题，且编程简单。 将物流中心选在与所有点对距离最近的那个点即可。

并创建以下几个类完成网络关系图的存储及最短路径计算，如表 1示。所

表 1 i sa法类及变量 Dj t算 kr

4路径分析设计 实际生活中，城市道路网的表现形式一般为数字化的矢

量地图，其网络空间特征的交叉路口坐标和道路位置坐标借助于地图上的图形来识别和解释的。要对城市道路网运用 D— i js a kt算法求解最短路径，首先必须抽象城市道路网络为网络 r图论中的网络图，另外，系统要求计算道路上任意两点间的最短路径，而传统 Djs a i t算法求解范围局限于任意网络节点 kr间，不能满足要求，必须进行改进

。41系统工作流程设计 .

5路径效果分析

随着 3术的飞速发展，“字城市”成为更高层次的 S技 数

追求，人们越来越多地要求从三位空间处理问题。建立以配

送为中心的物流服务体系。配送是商品市场发展的产物，随

着大批量、少批次的物流配送活动逐步被小批量、多批次所

随着城市建设的加快，城市道路网络经常发生变化，为避免经常改写代码，增强程序的健壮性和提高最短路径分析的运算效率，系统一般直接从拓扑文件提取道路网的网络拓扑结构并加载到内存中，一旦道路更新后，仅需重新抽象城市道路网络为网络图并生成拓扑文件即可。

取代，个性化、多样化的市场需求越来越占有更多的市场份额，配送已成为电子商务时代物流活动的中心环节和最终目

的。因此，一系列物流活动必须围绕组织配送表现出活跃的

市场机制。物流企业内部的所有部门和人员都应面向配送、

面向市场、面向客户。此外，物流企业要改变单一送货的观

念，协助电子商务公司完成售后服务，提供更多的增值服务

一

2一 0

SFW R EEOM N N EIN O rA EDVLP ET DDS A G内容，如跟踪产品订单、提供销售统计和报表等。只有这样，才能紧跟电子商务的步伐，不被市场所淘汰。 本文讨论了在物流配送时使用最短路径分析的 Dj r算 it sa

软件开发与设计【1王春燕，张华.遗传算法在配送中心选址中的应用[ 3 J]物流科技，20,(: 1- 1. 0 7 4)1 1 13 【】张斌武，王勤，余维燕.求解 H mmn距离下的最短路改 4 a ig进问题的一个近似算法[兰州理工大学学报：2 0, J]. 0 83 () 8 1 0 4 4:9 - 0 .

法设计。使得在配送时能够选择到配送点最短路径，降低配送成本。通过多次实验表明采用该算法准确、可靠，为路径分析在物流中的应用进一步扩展奠定了基础。

【】花玲玲 .基于 GS空间分布特征的 Djs a短路径算法 5 I i t最 kr研究 .重庆大学硕士论文，20,0: - 0 7 4 34作者简介

参考文献[】宗云.我国电子商务中物流配送存在的问题及对策[ . 1 J科 1技广场，20,

6 8 2 . 0 8:2— 9 【】莫海熙，郜振华，陈森发 .基于 A P和目标规划的物流配 2 H送中心选址模型【 .公路交通科技，2 0, f): 0 13 J 1 07 5 1~5. 5 (上接第 1页 ) 8en d; e nd; e d; n

凡金伟， (9 0 ) 18一，助理讲师，学士学位，研究方向：计算机硬件维修与故障排除。 吕康， (9 2 ) 18一，助教，学士学位，研究方向：计算机网络。

然后，双击“看”的按钮，编写代码用来查看并显示查移动存储介质的盘符。具体代码如下所示：poe ueT om1 uo 1 lk (ed rT jc); rcd r F r . t n Ci S n e: Ob t B t c ebe i gn

fr .b l.at n:p;,示在标签控件中 om1ae2C pi= p/ 1 o显e d; n

最后，双击“除”的按钮，编写代码查看并删除移动删存储介质中的 A t u . f件。这里可以利用 FlE is断 uo ni文 r n i x t判 e s

指定文件是否存在，再利用 D le i e tFl e e删除文件。具体代码如下：

图 2执行删除后

4结语 以上就是利用 B r n e h编写的一个删除 A trn n ol dD l i a p u u .f o i

po eueT om1 u o 2 l k (e drT jc); rcd r F r . t n C i Sn e: Ob t B t c ebe n gi

病毒残留文件的程序。通过这一程序可以轻松查删 u盘中的A t u .f件，从而解决用户无法正常双击打开存储介质根 u rn n文 o i目录的问题。当然，这个程序还有很多可扩展之处。例如：

iFl xs P+: uou . f t n, f iE i s(P trni h/文件 e t￣ n ) e查找 De t i p+A uou . f,除文件 le l p A trni '/ e F e( n)删es le

可以将程序的界面隐藏，后台实时运行。一旦监控到新接入息提示

S o Mesg (未找到该文件！ ); h w sae e d; n

的 U B设备存在有目标文件，即执行自动删除。另外，还可 S

3编译运行 . 3

以对查删文件的类型作自定义的功能。如果以后出现的问题文件可能不是 A t u . f uo ni,那

么就定义其文件名、文件类型， r n从而长期、有效地帮助计算机用户解决此类问题。

在 B r n e h中保存、编译运行程序。将一个受到病 ol dD l i a p毒感染，并存在病毒垃圾文件 A t u .f件的 U盘安装到 uo ni文 r n

计算机中。点击“查看”按钮，程序显示 u盘的盘符，点击“除”按钮，程序自动清除 A trni文件。程序运行效果删 uo .f u n如图 1罔 2所示。和

参考文献【】闫海忠，张俊.计算机 U B接口病毒揭密和清除【 .电 1 S J]脑编程技巧与维护，2 0; () 7— 9 0 7 5: 4 7 .

【】孟晋.计算机侵入 atrn病毒的预防和查杀方法[ 2 uou J].汉 0, t, ^ r I H r、Ir …矾●霜 .} …豳魏慧蒜棼薯^。嚣蒡

№围峥 X

。 r

中科技，20; f:4— 8 07 5 84. )

A trn文件 uou

【】Mak us oi,刘海蜀 .管理系统中自动运行程序的利 3 rR s nvc i h器—— A tmn J Wi o s& N t gz e国际中文 uo s【]. n w d e Maai: n版， o5 f 5—7 2o; 1 45 . ):

: .

,

{ i}

≥ t{舢口

【】董富治，李晶.D lh下实现 u盘病毒的自动清理【 4 e i p J】.电脑编程技巧与维护，20; (:8— 5 0 8 4 3 8 . 1 【】张一品，李梅莲 . D L H 5在 E P I中实现系统安全的新方法

匡匿

曼；— J 塑J—■鞴黧霪蓊鎏

[许昌学院学报，20;2 5:8—0 J】. 0 4 3( ) 79 .作者简介

图 I执行删除前

刘婷婷，女 (9 2 ) 1 8一，助教，主要研究方向：计算机应用和计算机基础教育。

一

2— 1

本文来源：https://www.bwwdw.com/article/7vyj.html