技术 与方法 物流技术2015年第34卷2月刊(下半月)
doi：l0．3969／j．issn．1005-152X．2015．02(2)．035
基于Dijkstra算法的区域物流网络配送路径优化
曹振华 ’，王宇翔
(1．河南省理工中等专业学校，河南 郑州 450008；
2．上海工商外国语职业学院 机电与信息工程系，上海 201399)
[摘 要】分析区域物流网中的配送路径距离和运输成本之间的关系，针对区域物流网的配送路径选择问题，通过 Dijkstra算
法建立单源最短路径的求解模型，求得配送中心到配送点 i、配送点 i到配送点j之间最短的矩形路阵。通过模型对最优化配送路
径方案进行求解，从而为物流配送中心调度提供理论数据，通过仿真实验验证了该配送路径选择的可行性和正确性。
【关键词】区域物流网络；Dijkstra算法；配送路径优化
【中图分类-~-]F252．14；F224 [文献标识码】A [文献~ -]mo5—152X(2015)02(2)一0146—02
OptimizationonRegionalLogisticsNetworkDistributionPathsBasedonDijkstraAlgorithm
CaoZhenhua ，WangYuxiang2
(1．HenanPolyt~hnieSchoolofScience＆Engineering，Zhengzhou450008；
2．1)epartmentofMeehatronies&InformationEngineering，ShanghaiIndustry
． ＆(~ommerceForeignLanguageCollege，Shanghai20l399，China)
Abstract：In this paper，we analyzed the relationship between the distribution path distance and the tran p0rtati0n cost in the regional logistics
network．Aimingattheproblemsofpathselection，weestablishedthe solvingmodelofthe shortestmonophyleticpathbyapplyingDijkstraAlgorithm，
f al~ulatingtheshortest rectangularpathfromthedistributioncentertothedistribution spotsiandj．Solvingtheoptimizeddistributionpathproblem
throughtheme,tel，weprovided solnetheoreticaldatatothedispatchingofdistributioncenter，andverifieditsfeasibilityandvaliditythroughthesin-
ulati~in．
Keywords：regionallogisticsnetwork；Dijkstraalgorithm；distributionpathoptimization
1 引言
货物的配送不仅影响着企业的服务质量而且在很大程度
卜决定着企 的成本。据统计，物流业运作成本的 80％都集中
在物流配送环节。随着我国宏观政策对于经济发展的支持，内
需进一步扩大，人们对于货物的配送有了直接的需求。在这个
过程中，配送方式的选择至关重要，直接影响着物流服务的水
半以及配送成本。近年来众多学者对于物流配送中心选址以
及配送路线的设定进行了相关研究 ，并且取得了一定的成果。
但是现存的算法都无法对模型的现实状况进行准确的描述，
只能从侧面反映配送，因而无法得出最优的配送方案。近年来
⋯现的 论与复杂网络的知识 ，给配送模型的建立以及最小
成本 送厅案的选取提供了切实可行的理论依据。利用复杂
网络可以将物流配送馍型转化为实际的网络路径计算 ，配送
中心以及客户都可以看作是复杂网络中的节点 ，该配送模型
的数学描述就是从配送点出发 ，经过所有或者部分客户节点
后，返回到配送中心的配送成本最小化问题。配送过程中每件
配送商品的单位距离运输费用是固定的，这样就可以将相应
的最小成本问题转化为路径问题。本文采用 Dijkstra算法建立
了物流配送最小成本模型。
2 基于Dijkstra算法的配送路径优化模型构建
2．1 区域物流网络与配送路径
对物流配送实际问题的抽象模型化也就是将物流配送过
程中的主要要素以及要素之间的关系通过合理的方式表现出
来。要素主要包括配送人员、配送中心位置 、客户相对于配送
中心的位置以及从配送中心到达客户地址的所有可能线路，
另外还包括商品的种类以及该种类商品配送单位距离的成本
等。上述各要素构成了物流配送的复杂网络配送模型。在复杂
网络中起点可以是任意一个配送中心，配送人员要通过将货
物运输到客户所在的地址完成相应的配送。从代表配送中心
的任意一个节点出发，途径部分或所有客户所在地的路线在
复杂网络中是节点与节点之间的连接线段，线段的长度代表
了实际路径的长度。
[收稿Et期]2015一O1—06
[作者简介1 篓华 ? 晏， 毫商量 ， 南省理工中等专业学校讲师，电子商务教研室主任，研究方向：电子商务和物流；王宇翔 ( 3
一 )，女，上海人，上海工商外国语职业学院机电与信息工程系讲师
，
研究方向：信息管理与软件开发。 。。” ⋯
- 146~
曹振华，等：基于Dijkstra算法的区域物流网络配送路径优化 技术与方法
在所抽象的物流配送复杂网络中，配送中心的位置选择
以及配送路线的确定是提升配送服务质量、降低配送成本的
关键。一旦配送中心选择与配送路径选择不合理就会造成配
送成本的攀升以及配送时间的延误 ，进而势必会影响到企业
的生存。所以本文主要利用复杂网络理论来解决配送中心的
选址以及配送路线确定问题。
2．2 Dijkstra算法下的路径选择
Dijkstra最基本的作用是计算两个节点之间的最短路径。
假设 G=(V，E)为本文所抽象的物流系统配送模型图，其中E为
物流配送路线的集合，v是复杂网络中节点的集合，该集合包
括物流配送中心与客户所在位置。利用该算法可以通过得到
任何点到配送中心的距离以及客户之间的距离来确定最终的
配送方案，使得配送的距离最小。该复杂网络中节点与节点之
间的位置是确定的，节点与节点之间的路径可以是一条或者
多条，配送者的任务就是从配送中心出发遍历完所有的客户
再回到配送中心并使走过的路程最短，本文将图 1所描述的
复杂网络模型作为建模依据。
图 1 复杂网络模型
2．3 建立模型
图 1中的复杂网络模型可以用邻接矩阵 A={aij)来描述 ，若
aij=0，则表示节点i与j之间没有可以到达的路径。如果该值为
1则说明二者之间有路径可以到达 ，得到的邻接矩阵如下所
示 ：
=
0 l
l O
O 1
O 0
O l
0 l
0 O
1 0
0 l
0 1
l 0
1 1
1 0
1 l
1 1
1 O
1 0
0 l
公式(1)中只是体现了节点之间有无路径连接的问题，但
是并没有体现节点之间连接路径的大小，本文用加权系数来
表示节点之间路径的大小，加权系数的定义如下：
fW ，aij=l
Wij=10,i=j
I∞．alj O
(2)
通过加权系数的规定以及复杂网络中节点与节点之间的
路径大小关系可以得到如下结果 ：
A =
O 2
2 0
o。 2
o。 oo
2 0
。。 2
∞ o。
O ∞
0 3
2 O
3 ∞
3 2
2 。。
3 2
3 2
∞ 0
0 。。
∞ O
(3)
公式(3)中第i行与第j列的元素wi 表示节点i和j之间
路径的大小。如果要得到配送的最短路径 ，就要对所有的配送
方案进行遍历，然后找出最佳的配送方案。在这之前要对复杂
网络中所有的节点进行编号以便于处理。首先需要找到每一
个客户点到达其它节点的最短路径，然后进行标注。其计算方
式如下：
D=mm{D ，D ．】+W，，} (4)
根据式(4)可以得到所有节点的最小距离矩阵 L：
离。
L =
1l ，l2 ⋯ f1
，2 ⋯ ，：
： ⋯
(5)
公式(5)中的元素 代表了节点 i到节点 j之间的最小距
3 仿真实验与分析
选取我国某个小型城市，对其物流配送点的分布情况进
行分析然后进行路径优化。该城市有 3个配送中心，客户点为
24个，24个点的坐标见表 1。
表 1 配送点的坐标
(4，5) (8，1t) (25，12) (32，5) (36，5) (38，9)
(46，6) (5t，10) (5 7，7) (4，22) (11，19) (22，23)
(3 4，19) (37，18) (3 9，16) (5，41) (8，39) (25，42)
(7，47) (8,27) (25，12) (6，49) (11，42) (25，39)
通过式(6)可以计算得出配送距离。
= ∑∑ (6)
i=1 y=l
其中，8 为 0，1变量 ，若路径 ij包含在配送路径中，则其
取值为 1，否则为 0。
通过公式(7)可以计算总的配送时间：
= ∑∑t (7)
江1 j=1
分别利用人工方法和Dijkstra算法确定最优路径，计算出
人工方式总的配送距离为 89km，配送时间为 1．3h；采用本文的
算法所得方案的配送距离为74km，配送时间为 O．92h；人工所
确定的路径要比本文算法所计算出的路径多出 15km，所花费
的时间多出 0．38h，所以本文所提供的针对物【下转第 191页)
- 147-
李玲：电子商务环境下供应链的最优销售渠道策略 供应链管理
万_一石■≥0，双渠道供应链中的制造商和零售商都能获得比
单渠道情况下更多的利润 ；
(2)当 o≤ ≤ 时 ， 一 0且 一 0，双
渠道供应链中的制造商利润低于单渠道情况下得到的利润，
而双渠道供应链中的零售商利润高于单渠道情况下得到的利
润；
(3)当 2≤ ≤ 3时，石：一刀 o且 石 一石 ≤0，双
渠道供应链 中的制造商利润高于单渠道情况下得到的利润 ，
而双渠道供应链中的零售商利润低于单渠道情况下得到的利
润。
因此，在双渠道供应链中占据领导地位的制造商应想方
设法获取消费者对网络直销渠道认可程度的信息，据此确定
参数的范围，从而选择最优的销售渠道以获取最大利润。
5 结论
本文研究 了电子商务环境下供应链的最优销售渠道策
略，分析了双渠道供应链成员的销售价格和服务水平决策、制
造商和零售商的利润分配以及销售渠道的选择等。研究发现：
当制造商既使用传统零售渠道又采用网络直销渠道时，会刺
激零售商提高其服务水平，零售商的利润随服务水平的提高
而增大 ；零售商的最优服务水平随着消费者对渠道服务敏感
度的上升而增加 ，制造商也能从中获得更高的利润；双渠道供
应链的总利润高于单渠道供应链的总利润，双渠道供应链的
总利润随着消费者对网络直销渠道认可度的提升而增加；在
供应链中占优的制造商可以根据消费者对网络直销渠道的认
可度，来选择单销售渠道或双销售渠道策略。
[参考文献】
[1]Tsay A A，Agrawal N．Channel Conflict and Coordination in the E—Com—
merce Age[J]．Production and Operations Management，2004，13(1)：93—
110．
【2]Yao D，Liu J J．Competitive Pricing of Mixed Retail and E-tail Distribution
Channels[J]．Omega，2005，33(3)：235—247．
[3]Cattani K D，Gilland W G，Swaminathan J M．Boiling Frogs：Pricing Strate—
gies for Amanufacturer Adding a Direct Channel that Competes with the
Traditional Channel[J]．Production and Operations Management，2006，15(1)：40-
57．
D]Kurata H，Yao D，Liu J J．Pficing Policies under Direct VS．Indirect Channel
Competition and National VS．Store Brand Competition[J1．Eumpean Journal
ofOperational Research，2007，180(1)：262—281．
[5】王虹，周晶．具有风险规避参与者的双渠道供应链最优策略研究[JJ．计
算机集成制造系统，2009，15(1 1)：2 241—2 246．
[6】陈树桢，熊 中楷，梁喜．补偿激励下双渠道供应链协调的合同设计[J]．
中国管理科学，2009，17(1)：64—75．
[7]Chiang W K．Product Availability in Competitive and Cooperative Dual-chan—
nel Distribution with Stock-out Based Substitution[J]．European Journal of
Operational Research，2010，200(1)：11 1-126．
[8]Yan R，Pei z．Information Asymmetry，Pricing Strategy and Firm’S Perfor—
malice in the Retailer-multi-channel Manufacturer Supply Chain[J]．J0ur_
hal ofBusiness Research，201 1，64(4)：377—384．
(上接第 1 47页)流配送的算法是有效的。
案
图3 Dijkstra算法确定的物流配送方案
通过对两种不同方式确定的物流配送方案的对比 (如图
2、图 3所示 )可以发现 ，利用 Dijkstra算法得到的物流配送方
案配送完所有客户所行走的路程要比人工规划方案所行走的
路程短得多，配送成本大大降低了，同时也在一定程度上提高
了服务的质量。
4 结语
由于配送过程是物流成本产生的主要环节 ，所以如何对
配送环节进行有效规划并提高配送效率 、降低配送成本就成
了物流业面临的主要问题。本文利用 Dijkstra算法得到最小路
径的模型。通过该模型得到配送的最佳方案也就是最小成本
方案，不仅在一定程度上降低 了物流配送环节的成本，也间接
提高了物流服务质量。
【参考文献】
[1]任春玉，王晓博．电子商务环境下物流配送中心选址决策与评价方法
研究叨．商业研究，2006，(23)．
[2】于雷．模拟并行蚁群算法的绿色物流最小油耗配送路径优化【D1．上
海 ：上海交通大学，2013．
— —191-
