赵丽娜+张丽华+窦冰洁+孙蕊

摘 要：文章研究了一种特殊的旅行商问题——带油耗的单商品取送货的旅行商问题，建立了该问题的非线性混合整数规划模型，并且根据文章问题的特征，设计了求解它的一个贪婪式启发式算法和一个遗传算法，给出一个例子对算法进行了说明。

关键词：运筹学；单商品旅行商问题；油耗；遗传算法

中图分类号：F252.14 文献标识码：A

Abstract： In this paper， a kind of special traveling salesman problem-the one-commodity pickup and delivery traveling salesman problem with fuel consumption is studied， a non-linear mixed integer programming model for this problem is built， and according to the characteristics of the problem in this paper a greedy heuristic algorithm and a genetic algorithm are designed， an example is given to illustrated the algorithms.

Key words： operational research； one-commodity pickup and delivery traveling salesman problem； fuel consumption； genetic algorithm

0 引 言

单商品取送货旅行商问题（1-PDTSP）是传统旅行商问题（TSP）的一类新变种。与TSP相比1-PDTSP的特殊之处在于：一个特殊的城市作为车场，其它城市作为客户，客户根据其需求类型可被划分为送货客户和取货客户两类，而所谓的送货客户（需求量小于0）与取货客户（需求量大于或等于0）分别指需要一定数量的货物被送达和被取走的客户。1-PDTSP的特殊性还体现在货物上：送货客户所需要的货物不仅可以来自车场，还可以直接来自于取货客户，即从取货客户处取回的货物可以直接供送货客户使用，此外，1-PDTSP还假设车辆必须从车场出发，并且最终回到车场，车辆的容量给定并且有限，车场有足够的货物供各客户使用，也具备足够的空间存放取回的货物。

1-PDTSP由Hipólito和Juan-José[1]于2003年首次提出，并且在2004年[2]他们给出了一种分支—切割（branch-and-cut）算法对其进行求解，该算法可以求得1-PDTSP的精确解，但当问题的规模较大时，分支—切割算法时间太长，因此他们在同年[3]以及2007年[4]、2009年[5]提出了几种启发式算法来求解1-PDTSP；2006年Fan Wang等人[6]给出求解1-PDTSP的一个关于路径和树形拓扑结构的优化算法；……