基于TSP模型的德邦物流某网点循环取货路径研究

黄春江 李玉峰 王鹏飞

摘要：近几年，国内零担行业迅猛发展，期间，德邦物流、佳吉快运、天地华宇等公司得到迅猛发展。但是我国零担物流企业众多，中小企业为了生存只能通过竞相压低价格来占有市场。文章在分析了德邦物流某门店发展现状及存在问题的基础上，运用TSP基本原理，收集到相关数据，规划上门服务循环取货路径，提高取货效率。

关键词：TSP模型；循环取货；德邦物流

中图分类号：F224 文献标识码：A 文章编号：1009-2374（2014）02-0021-03

第三方物流的迅速发展，为零担运输企业提供了更多的市场机会，但同时也使市场竞争更加激烈。由于行业进入的壁垒较低，许多小企业或个人进入零担运输市场，使得价格竞争非常激烈，对规范的市场竞争不利。第三方物流企业大打“价格战”，各企业利润空间狭小、生存压力大，如何降低企业成本是企业经营者长期思考的问题。

1 TSP模型及求解

1.1 TSP简介

旅行商问题（TSP），也称为货郎担问题、巡回销售问题。该问题是一个典型的组合优化问题，可以简单地描述为：设有N个城市以及设定城市之间的旅行费用，找一条走遍所有城市且费用最低的旅行路线。旅行商问题是单回路运输问题中最为典型的一个问题。

配送路径优化问题可以说是对旅行商问题加以一定限制而形成的，这些限制包括：客户有一定的货物需求（货供应）数量且要求货物在一定的时间范围内送达（或取走）、配送车辆的装载量限制及一次配送的最大行驶距离限制等，即车辆路径优化问题是一个多约束的旅行商问题。

单回路运输问题是指在运输路线优化时，在一个节点集合中，选择一条合适的路径遍历所有的节点，并且要求闭合。单回路运输模型在运输模型中，主要用于单一车辆的路径安排，目标是在该车辆遍历所有用户的同时，达到所行驶距离最短，这类问题的两个显著特点：（1）单一性，只有一个回路；（2）遍历性，经过全部用户，不可遗漏。

1.2 TSP数学模型

TSP问题的模型可以描述为：在给出的一个有n个定点网络（有向或者无向）要求找出一个包含n个定点的具有最小消耗的环路。任何一个包含网络中所有n个定点的环路被称为回路。在旅行商问题中，要设法找到一条最小耗费的回路。既然回路是包含所有定点的一个循环，故可以把任意一个点作为起点（也是重点），这也是TSP模型的一个特点。

TSP模型的数学描述为：

假设连通图H，起定点集A。

定点间的距离为：

满足：

决策变量：

求解TSP模型时，如果要得到精确的最优解，最简单的方法是枚举法。对于小型问题，这也是一种十分有效的方法。但是对于大型问题，由于枚举法的列举次数为（n-1）次，若用枚举法将是无法想象的。

另外，运筹学领域的证书规划的方法也可以用于结局部分TSP模型，其中分支定界法是一种比较实用的算法，但是该算法也是只能对一部分中小规模问题的TSP模型进行求解，对于大多数问题的求解都存在一定的难度。由于此次研究是针对德邦某门店的循环取货实证研究，主要采用Lingo软件求解。该门店的特点如下：（1）需要规划的取货点少，规模不大；（2）取货方式满足旅行商问题的条件；（3）Lingo软件能够对小规模旅行商问题求解。

2 Lingo软件程序及建模

2.1 Lingo程序简介

Lingo全称是Linear Interactive and General Optimizer的縮写—交互式的线性和通用优化求

解器。

Lingo是使建立和求解线性、非线性和整数最佳化模型更快、更简单、更有效率的综合工具。而且Lingo能够提供强大的语言和快速的求解引擎来阐述和求解最佳化模型。

2.2 Lingo建模

简单的模型表示：

model：

sets：

cities/1..7/：level；！level（！）=the level of city；

link（cities，cities）：

distan

ce，

x；！x（i，j）=1 if we use link i，j；

endsets

data：

distance=

enddata

n=@size（cities）；！the model size；

min=@sum（link（i，j）|i #ne# j：distance（i，j）* x（i，j））；

@FOR（cities（i）：

@sum（cities（j）|j #ne# i：x（j，i））=1；

@sum（cities（j）|j #ne# i：x（i，j））=1；

@for（cities（j）|j #gt# 1#and# j #ne# i：

level（j）>=level（i）+x（i，j）-（n-2）*（1-x（i，j））+（n-3）*x（j，i）；

）；

）；

@for（link：@bin（x））

@for（cities（i）|i#gt#1：

level（i）<=n-1-（n-2）*x（1，i）；

3 实证研究

3.1 德邦物流简介

德邦是国家“AAAAA”级物流企业，主营国内公路运输业务。截至2013年10月末，公司已开设直营网点4200多家，服务网络遍及全国，自有营运车辆7200余台，全国转运中心总面积超过88万平方米。

德邦物流始终以客户为中心随时候命、持续创新，始终坚持自建营业网点、自购进口车辆、搭建最优线路，优化运力成本，为客户提供快速高效、便捷及时、安全可靠的服务体验，助力客户创造最大的价值。

3.2 德邦物流某网点现状

本文将以德邦物流某网点的上门取货路径做实证

研究。

该网点目前有一名门店经理、三名营业员以及一名驾驶员。门店订单来源主要来源于客户上门订单、电话订单和网络订单。对于需要上门取货的客户，门店经理根据排班表由一名营业员陪同司机驾车外出取货。而为了达到较高的客户满意度，门店都是在客户有需求的时候上门，一次出门提取的商家只有2～3家，并且出门时间不确定，完全根据客户的需求。这样的做法导致的结果是多次上门取货汽车行驶距离长，燃油成本高，并且驾驶员需要全天处于待岗状态，休息时间不确定，行车安全存在隐患。

3.3 路径优化实证

通过与服务商家协商制定配送时间表，保证取货及时以及减少燃油成本，同时驾驶员也能有足够的休息时间，确保行车安全。

本文选取了门店的几个长期服务商家进行实证研究，其中①点为门店所在位置，③点为工业园区，其中包含十余家企业，因距离近合并为一点。

各个节点之间的距离如表1所示。

各个节点之间的行车时间如表2所示。

将表1和表2中的数据输入模型，应用Lingo软件建模运行求解得到该问题的最短路径为①→②→③→⑤→⑥→⑧→⑦→④→①，最短距离为56.6公里。

通过与相关商家协商，安排了如表3所示的行车时间表：

表3

节点 停留时间

① 14∶00（出发时间）

② 14∶04～14∶09

③ 14∶13～14∶53

⑤ 14∶09～15∶14

⑥ 15∶35～15∶40

⑧ 15∶46～15∶51

⑦ 15∶54～15∶59

④ 16∶26～16∶31

① 16∶45（回程时间）

注：根据对每次取货流程耗费时间的记录，一般耗时4分钟，我们选取五分钟作为一个节点的标准时间；由于节点③处于工业区，周边有十余家服务商家，停留时间为40

分钟。

通过实证研究，循环取货路径得以优化，行车距离减少，企业燃油成本能够大幅減少，并且通过与商家协商，加强了伙伴关系，也提高了服务质量。

参考文献

[1] 赵春英，张铃.求解货郎担问题（TSP）的佳点

集遗传算法[J].计算机工程与应用，2001，37

（3）：83-84.

[2] 蒋长兵，吴承建，彭扬.运输与配送管理建模与仿

真[M].北京：中国物资出版社，2011.

[3] 谢金星，薛毅.优化建模与LINDO/LINGO软件

[M].北京：清华大学出版社，2005.

作者简介：黄春江（1993—），男，四川宜宾人，江苏科技大学经济管理学院物流管理专业学生，研究方向：供应链与物流。