第!"卷 第"期 运 筹 与 管 理 #$%&!"，’$&"
"(()年*月 +,-./01+’2.-2-/.34/’56/’/7-6-’0231-’3- /89&，"(()
收稿日期："((":!(:!!
作者简介：池洁（!;<=:），男，重庆市人，重庆交通学院副教授，主要从事网络优化及应用研究；李莉（!;>>:），女，重庆市人，重庆交通学院教师。
物流中配送区域与配送路线的网络优化法
池洁， 李 莉
（重庆交通学院 管理工程系，重庆*(((>*）
摘 要：本文讨论物流中配送区域的划分与配送路线的选择问题，应用网络、图论的优化方法，解决配送区域的
划分与配送路线的选择问题。
关键词：运筹学；货物配送；网络优化；最短路；动态规划
中图分类号：+""* 文章标识码：/ 文章编号：!((>:)""!（"(()）(":(!"):(<
!"#$%&’’()*#+,+-"."#/%0(%12"3+4"&5&"65702"3+4"&86#/(97:%;3(#+<(
341?@A，B1B@
（!"#$%&’"(&)*+$($,"’"(&-(,.(""%.(,，/0)(,1.(,2.$)&)(,3(4&.&5&"，/0)(,1.(,*(((>*，/0.($）
5=(#&6<#：1CDE@F8G8A9，DEA$8D@H@IA89$J%AHF$KLA%@MA9G9AGGCL8GDE@C%$N@FD@OFG9AFDPL@AL&0EA$8D@HG%
HADE$LF$KLA%@MA9G9AGGCL8GDE@CCADQ$9RG9A89AFACDAL&
>"?$%&0(：8ESF@OG%L@FD9@JPD@$C；FE$9DAFD8GDE；LSCGH@O89$N9GHH@CN
( 引言
物流学是当代有影响的新学科之一。他以物的动态转过程为主要研究对象，揭示了物流活动的内在
联系，使物流系统在经济活动中从潜隐状态显现出来［!］。
要实现物流的时间效益和空间效益，物流系统中有一重要的环节，即：物流的配送体系。对配送网络
体系来说，有单层次或多级、多层次网络体系，企业可根据自身的经营规模、范围、种类等，确定建立何种形
式、规模的配送体系。但无论建立何种类型配送体系，都存在下两方面的问题：
（!）定每个配送中心合理的配送区域；
（"）配送过程中配送路线的选择。
由于在货物配送过程中，运输费用是成本构成主要因素之一，因此，确定运输距离最短的方案，是制定
配送计划应该考虑的问题。本文将采用网络图论的方法对问题（!）、（"）进行讨论。对问题（!），通过转化
可将该问题化为有次限制的最小支撑树问题［"］；对问题（"），本文对问题（"）采用动态规划原理方法，并给
出该问题的动态规划解法，为制定合理的配送路线方案提供有效的方法。
! 配送范围的划分
!"! 问题的图论表示
对与区域配送中心和基层配送中心来说，其特点是：活动范围较小，即送的货物以小批量为主，即直接
向用户配送物资；有时又得按照各个零售商的要求配送物资。
假如某企业以在某城市（地区）建立了6个配送中心（(!6），该城市有(T6个居民区（接货点），每
万方数据
个配送中心的配送能力，以可承担多少个居民区（接货点）来确定，!"（"!"，#，$，⋯，#）表示第"个配送中
心可承担!"个居民区（接货点）的配任务，每个接货点与配送中心之间都有道路连通。
假如每个配送中心的配送范围的划分，以运输距离最短为目标，可将问题（"）转化为网络中的优化问
题。
设$!（%，&，’）是以%为顶点集，以&为边集，以’ 为赋权集的连通图［$］。其中：
（"）%!｛(%，("，(#，($，⋯，()｝表示图的点集
（#）%#!｛(*"，(*#，(*$，⋯，(*#｝为配送中心构成的点集，%#!%；
（$）%"%#表示)&#个接货点：
（’）&!｛+*"!（(*，("）：(*，(*#%｝，+*"表示(*与("之间直接有道路相连；
（(）’!｛,（(*，("）!,*"：（(*，("）#&｝，,*"表示(*与("之间直接道路的长度。
设图$的支撑子图-!（%，&（-），’（-）），若：对任何(*#%有：./（"）!$｛("：（(*，("）#&（-）｝$
（表示(*在图-中的次），如果要使图$的支撑子图-满足配送中心与接货点的关系要求，就必须满足以
下条件：
（)）每个接货点至少有一个配送中心负责送货，即：对任意(*#%"%#，存在("#%#，使(*与("在&
（-）中有路连通；
（*）每个配送中心负责的范围不能超过配送能力，即：对任意("#%#，./（"）!$(*：(*与("在图-中
有路连通，且(*#%"%#$，./（"）%!"。
设0是满足条件（1）图$中所有支撑图组成的集合
’（-）2+,- &
（*，"）#&（-）：-#0
,（*，"）
（"）
当0是满足条件（)）、（*）图$ 中所有支撑图组成的集合，对引言中提出的问题#可下列问题的优
化：
’（-）!+,- &
（*，"）#&（-）；-#0
,（*，"） （#）
".#将问题转化为最小支撑树问题
首先对图$进行扩充，在图$的结点外再增加一个结点()/"，在结点()/"与%#之间分别增加一条
边，得到图$%!（%%，&%，’%），其中：%%!%’｛()/"｝；&%!&’｛()/"，("）：("#%#｝；
’%!’’｛,（()/"，("）!%：("#%#｝。
定理! 设-%是图$%的最小支撑树。构造如下-：%（-）!%%"｛()/"｝!%；&（-）!&%（-%）"
｛（()/"，("）：("#%#｝。则-为（"）的最优解且’（-%）!’（-）。
证明 按照-的构造方法，-显然是（"）的可行解。
因为,（()/"，("）!%，("#%，所以’（-%）!’（-）。
如果-不是（"）的最优解，设-(是（"）的最优解，’（-(）)’（-）!’（-%）。构造如下-"：
%（-"）!%’｛()/"｝；&（-"）!&（-(）’｛（()/"，("）：("#%#｝；,（()/"，("）!%，("#%#。
-"是图$%的支撑图，在图-"中，对任意("，(*#%#两点，通过点()/"连通。按照条件（1），对任意
(*#%"%#，存在("#%#，使(*与("在&（-(）中有路连通，&（-"）*&（-(），-"是图$%的连通支撑
图，显然’（-(）!’（-"）+’（-%），与设-%是图$%的最小支撑树矛盾。故-是（"）的最优解。
定理" 设-是图$中问题（"）的最优解。构造如下-%
%（-%）!%’｛()/"｝；&%（-%）!&（-）’｛（()/"，("）：("#%#｝；,（()/"，("）!%，("#%#。则-%是图
$%的最小支撑树且’（-%）!’（-）。
证明 由定理"的证明过程可知：-%是图$%的连通支撑图，假设图-%不是树，则在图-%中存在圈
3!（(*"，(*#，(*$，⋯，(*4），且$%（3）$!4+$；由图-%构造方法可得：&（3）,&（-）-5，否则&（3）!
｛（()/"，("）：("#%#｝，3!（(*"，(*#，(*$，⋯，(*4）不是圈，因此存在（(*，("）#&（3），使,（(*，("）!,*".
%。取-"!-%"（(*，("），-"也是图$%的连通支撑图，且’（-"）)’（-%），设-(是图$%的最小支撑
树，’（-(）%’（-"），与定理"的结论矛盾。因此定理结论成立。
’#" 运 筹 与 管 理 #%%$年第"#卷
万方数据
推论! 设!是图"中问题（!）的最优解，则在图""中#（$%#!）!#（!）$&。
证明 按照定理%的证明过程可得。
推论" 设!是图"中问题（!）的最优解，则对任意$’"(#()有且仅有一个$*"()，使$’与$*在
#（!）中有路连通。
推论%可以由定理!，定理%的结论和证明过程得出。
对问题（%），如果图"满足以下条件：对任意$’"(#()，存在$*"()，使$’到$*的最短路距离$
+*；%
$*"(,
+*&%&)。在图"一定存在满足条件（-）、（+）的支撑子图!，问题（%）存在最优解。
同理可证下述结论。
推论# 设!"是图""的最小支撑树：对任意$*"()，./（*）$+*。构造如下!：(（!）$("#
｛$%#!｝$(；#（!）$#"（!"）#｛（$%#!，$*）：$*"()｝。则!为（!）的最优解且0（!"）$0（!）。
上述过程表明：解问题（!）可通过求图""$（("，#"，0"）的最小支撑树；解问题（%）可应用文献［%］提
出的算法求解。由定理!、定理%、推论!、推%、推论’可得以下性质：对配送区域的划分明确，使每个接货
点只有一个配送中心负责送货。
例 如图为配送中心与接货点的分布图
图（"!）
在图中配送中心为(,$｛$"，$(｝，且+"$)，+($*；
0$｛1（"，!）$’，1（"，%）$’，1（%，!）$%，1（*，!）$’，1（%，’）$!，1（’，*）$)，1（’，)）$%，1（%，(）
$*，1（+，(）$’，1（+，,）$)，1（)，+）$%，1（,，(）$*，1（*，)）$’｝。
该问题配送中心$"，$(所确定的配送区域图为!（$"）、!（$(）
!（$"） !（$(）
% 送线路的选择
配送路线的选择问题是在配送中心的配送区域划分已经确定以后，对某个配送中心每次配送的要求，
)%!第%期 池 洁，等：物流中配送区域与配送路线的网络优化法
万方数据
所制定的配送路线的选择方案。
该问题与图论中的货郎担问题的区别，货郎担问题是指：一个推销员需要去!个城市推销产品，从某
个城市出发，经过其他!个城市一次且仅仅一次，再反回到原出发城市，试问，如何选择行程路线，使总路
程最短［!］。但在很多实际问题中，并不要求“推销员”去!个城市中的所有城市，而只要求去!个城市中
的某"（"!!）个城市，再返回到原出发城市，问，如何选择行程路线，使总路程最短，可称为不完整的货
郎担问题。例如：某销售商根据一段时间内的商品的销售情况，用送货车辆将商品送到各用户，如何选择
行程路线，使总路程最短等问题。
设某配送中心负责#个接货点$""｛%#，%$，%!，⋯，%#｝，%%为配送站，&"（$，’，(）由城市道路构
成的网络图，$"$"#｛%%｝，’，( 分别表示城市道路构成得边集，以及道路长度构成得权集。有一配送
任务，从%%配送出发，将货物送到"（"!#）个接货点$""｛%)#，%)$，%)!，⋯，%)"｝，并回到%%，问如何选
择配送路线，使送货路线最短。
记$""｛%)#，%)$，%)!，⋯，%)"｝$$%｛%%｝（"!#），&$"&""（注：$" 中的结点表示接货点，%%表
示配送站）。*是图&中从%%出发经过$" 中所有结点，返回到%%的所有闭链组成的集合（每条闭链为
*中的元），+,’*，且$"$$（+-）%｛%%｝，其中$（+,）表示+,上的结点，’（+,）表示+,上的边集。
&’( (
（)，.）’’（*）：+’*
/（)，.） （!）
求解问题（!）时，首先问题（$）求解得到的某配送中心配送区域划分图0.（%.’$1），在图&中还原成
图&子图&（0.），如：图0（%%）可还原成下图：
图（&（0（%%）））
再按照动态规划的方法求解。
按照动态规划的基本原理和方法。
（#）将问题的过程划分为" 个阶段（本次的" 个接货点），阶段变量1。
（$）状态变量（%.，-）：%.’$"，%.表示送货车辆从%%走到%.，-表示到%.之前途中所经过的接货点
的集合，-$$"。
（!）决策：表示为由一个接货点%.（%.’$"）走到另一个接货点%)（%)’$"）。
（)）最优指标函数：21（%.，-）"&’()’-
｛21*#（%)，-／｛%)｝）+&+).&｝（1"#，$，!，⋯，"）
其中，+)&+.)&分别表示%.到%)的最短路和最短路的里程。
边界条件为2%（%.，3）"&+%.&｝，."#，$，!，⋯，"。
例! 按图（&（0（%%））从%%途径$""｛%#，%$，%)｝返回%%，求最短环游路线及路程。
解 用动态规划方法，由边界条件可知：
2%（%#，3）"&+%，#&"!；2%（%$，3）"&+%，$&"!；2%（%)，3）"&+%，)&",
当1"#时：2#（%#，｛%$｝）"2%（%$，3）+&+$，#&"!+$"-
2#（%#，｛%)｝）"2%（%)，3）+&+)，#&",+!".
2#（%$，｛%)｝）"2%（%)，3）+&+)，$&",+-"##
2#（%$，｛%#｝）"2%（%#，3）+&+#，$&"!+$"-
2#（%)，｛%#｝）"2%（%#，3）+&+#，)&"!+!",
2#（%)，｛%$｝）"2%（%$，3）+&+$，)&"!+-"/
当1"$时：
,$# 运 筹 与 管 理 $%%!年第#$卷
万方数据
!!（""，｛"!，"#｝）$%&’｛!"（"!，｛"#｝）(!#!，"!，!"（"#，｛"!｝）
(!##，"!｝$%&’｛""()，*()｝$""
!!（"!，｛""，"#｝）$%&’｛!"（"#，｛""｝）(!##，!!，!"（""，｛"#｝）
(!#!，"!｝$%&’｛*(+，,(!｝$""
!!（"#，｛""，"!｝）$%&’｛!"（""，｛"!｝）(!#"，#!，!"（"!，｛""｝）
(!#!，#!｝$%&’｛+()，+(+｝$*
当$$)时：
!!（"-，｛""，"!，"#｝）$%&’｛!!（""，｛"!，"#｝）(!#"，-!，!!（"!，｛""，"#｝）
(!#!，-!，!!（"#，｛""，"!｝）(!##，-!｝
$%&’｛""()，""()，*(.｝$"#
由此可知最短环游里程为"#，线路有两条，%"（"-，""，"#，""，"!，"-）；%!（"-，"!，""，"#，""，"-）。
) 结束语
该算法开发成计算机软件后，在实际应用中，对货物配送路线方案的选择，效果较好。
参考文献
［"］张卫星/物流学［0］/北京工业大学出版社，!--!年"月/
［!］刘振宏，马种蕃，朱永津，蔡茂诚/具有次限制的最小树问题［1］/应用数学学报/",*-/)（"）："2"!/
［)］34’5617，089:6;<=/>9?@ABAC496D&:A7@@E&F?:&4’［0］/7%C9/GEHCI&C9/",J./
中国科协!""#年学术年会征文通知
中国科协!--)年学术年会将于!--)年,月")日至".日在辽宁省沈阳市召开，会前正式出版论文摘要文集。论文摘要文集将收录报
名参加年会主题会场和分会场交流的学术论文摘要，希望全国广大的科技工作者能将自己的最新科研成果展示于此。同时，本文集不保留
知识产权，作者可继续向其他刊物投稿。本文集由中国科学技术出版社出版。
请报名参加中国科协!--)年学术年会的代表，按照本通知的各项规定撰文和投稿。
一、学术年会的主题和会场设置
（一）学术年会的主题
!--)年年会的主题为：“全面建设小康社会：中国科技工作者的历史责任”。大会特邀报告将围绕年会主题以及科学技术的前沿领域邀
请报告人。
（二）会场设置及组织
会场分为大会特邀报告会场、主题会场和分会场。大会特邀报告会场主要内容为中国科协组织的大会特邀报告；主题会场将围绕年会
主题进行交流；分会场由有关全国性学会和辽宁省、沈阳市负责组织，进行以学科群分类的综合性学术交流。本文集只收录经专家审阅后
录用的文章摘要，为会议代表在会议期间的交流提供方便。主题会场和各个分会场均有编号，请作者根据文章内容选择所参加的主题会场
或分会场，并在个人报名表和论文摘要登记表中准确填写会场标题和编号，将论文摘要直接投递到负责各个会场组织工作的单位。
二、征文的范围
（一）主题会场
主题会场围绕本届学术年会主题“全面建设小康社会：中国科技工作者的历史责任”，可以考虑以下内容投稿：中国科技工作者在全面
建设小康社会中的历史责任和重要作用；关于全面建设小康社会的战略思考与政策建议；全面建设小康社会和科学技术发展；!-!-年中国
科技发展前景；走新型工业化道路：依靠科技进步和提高劳动者素质；完善科技服务体系的思路和方法等。
（二）分会场
分会场围绕各个分会场专题设定的内容投稿。
三、论文摘要的要求
（一）中国科协!--)年学术年会论文摘要的作者（包括在地方科协报名的作者），凡报名主题会场的将论文摘要直接投递到中国技术经
济研究会，报名各个分会场的将稿件直接投递到负责各分会场组织工作的全国性学会和辽宁省、沈阳市科协。以上稿件一律经专家评审筛
选后才可录用，编入文集。地方科协只负责组团报名，不再负责审阅论文。
（二）请作者按照前述学术交流主题与范围撰写论文摘要，于!--)年#月)-日前报送各个会场组织单位。
（三）论文摘要的征集、审定和推荐工作，将由各个会场的组织单位负责。有关全国性学会须组织专家对所征收稿件进行审阅把关，在论文
（下转第"--页）
第!期 池 洁，等：物流中配送区域与配送路线的网络优化法
万方数据
