论文部分内容阅读
摘 要：文章研究了一种特殊的旅行商问题——带油耗的单商品取送货的旅行商问题，建立了该问题的非线性混合整数规划模型，并且根据文章问题的特征，设计了求解它的一个贪婪式启发式算法和一个遗传算法，给出一个例子对算法进行了说明。
关键词：运筹学；单商品旅行商问题；油耗；遗传算法
中图分类号：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的一个关于路径和树形拓扑结构的优化算法；2009年赵方庚等人[7]给出一个遗传算法来解决此问题；2012年Nenad Mladenovic等人设计了求解1-PDTSP的变邻域搜索算法[10]，这些启发式算法都能较好地解决大规模1-PDTSP，然而由于1-PDTSP只考虑优化车辆总的行驶费用，而在当今社会，随着能源的短缺和环境污染的日趋严重，油耗问题成为人们关注的焦点，因此本文研究带油耗的1
-PDTSP，该问题到目前为止还没有人研究过，它与1-PDTSP的区别在于既考虑车辆的行驶费用又考虑车辆的载货量产生的耗油费用，这样一来，虽然两个问题的可行集是相同的，但最优解不同，下面举例说明。
设有1个车场，4个客户点，它们的需求及相互之间的距离分别如下列的表1和表2所示，车辆容量为10。
设单位距离费用为1，单位距离单位重量费用为1.2，于是所有可行解及相应的费用如表3所示。
所以不考虑油耗和考虑油耗的最优解分别为：1→2→4→5→3→1和1→5→3→2→4→1，说明带油耗和不带油耗的1-PDTSP是有区别的，求解后者的算法不适用于前者，本文第3节的例子也说明了这一点，因此本文根据带油耗的1-PDTSP的特点设计了一个贪婪式启发式算法和一个遗传算法求解它，其中的遗传算法是将文献[7]的遗传算法进行修改得到的。
1 带油耗的1-PDTSP问题及其数学模型
（4）计算可行解1、可行解2对本文问题的目标函数值，将目标函数值最小的可行解存储在一个1行3列的元胞数组的第2个元素里，该元胞数组的第1个元素存储1，第3该元素存储该解对本文问题的目标函数值的倒数，得到一条染色体。重复使用该方法生成100条染色体得初始种群。
交叉：
采用GA_1的交叉方法，但要将在可行邻居中挑选下一客户点的规则改为在可行邻居中挑选需求绝对值除以到未完成路径中最后一个客户点的距离最大者为下一个客户点。
变异：
采用GA_1的变异方法。
3 例 子
在本例中，客户数为70，本文用文献[7]中的方法生成例子： 车场的坐标为0，0，其它70个客户点的横纵坐标在-500，500范围内随机生成，每个客户的需求q在-10，10范围内随机产生，车场需求车辆容量为10，单位重量单位距离的运输费用是1.5，空载时单位距离的行驶费用是1。表4为各客户点的需求量，图1为车场和所有客户点的位置图。
应用贪婪式启发式算法和本文的遗传算法GA_2得到的本例的次优解相同，都为哈密顿回路：
0→27→14→58→34→43→47→32→1→57→51→40→26→21→48→61→18→41→37→35→23→59→29→3→16→53→52→31→66→15→44→4→65→8→54→36→46→30→69→11→62→39→67→9→25→28→56→22→68→42→64→50→55→63→38→12→20→45→70→24→5→19→60→33→2→6→49→7→10→17→13→0 该解记为Solution_1，它对本文问题的目标函数值为：236950/3=7.898331178012094e+04。
应用文献[7]中的遗传算法GA_1得到的求解不带油耗的1-PDTSP问题的次优解（该解也是本文问题的可行解）为哈密顿回路：
0→65→21→48→61→18→41→23→59→37→22→30→69→11→67→9→36→8→54→42→64→60→33→4→32→43→14→27→47→58→57→44→15→52→53→16→31→66→63→55→40→51→34→45→20→50→12→26→38→49→7→3→35→56→28→39→62→2→68→46→25→19→5→70→1→24→17→29→13→6→10→0
该解记为Solution_2，它对本文问题的目标函数值为：323222/3=1.077406446095206e+05。
显然对本文的问题而言Solution_1的目标函数值要远远小于Solution_2的目标函数值，因此求解不带油耗的1-PDTSP的算法不适合求解本文的带油耗的1-PDTSP。
4 结 论
由于近年来对油耗问题的关注，本文针对过去的1-PDTSP，提出了带油耗的1-PDTSP，这更具有现实意义。根据本问题的特点给出了求解算法，并通过例子对算法进行说明，结果表明本文给出的算法适合用于求解带油耗的1-PDTSP。
参考文献：
[1] Hernández-Pérez H， Salazar-González J. The one-commodity pickup-and-delivery traveling salesman problem[J]. Combinatorial Optimization （Edmonds Festschrift）， 2003，2570：89-104.
[2] Hernández-Pérez H， Salazar-González J. A breach-and-cut algorithm for a traveling salesman problem with pickup and delivery[J]. Discrete Application Mathematics， 2004，145（1）：126-139.
[3] Hernández-Pérez H， Salazar-González J. Heuristics for the one-commodity pickup-and-delivery traveling salesman problem[J].Transportation Science， 2004，38（2）：245-255.
[4] Hernández-Pérez H and Salazar-González J. The one-commodity pickup-and-delivery traveling salesman problem Inequalities and algorithms[J]. Wiley Inter Science， 2007，50（4）：258-272.
[5] Hernández-Pérez H， Inmaculada M， Salazar-González J. A hybrid GRASP VND heuristic for the one-commodity pickup-and-delivery traveling salesman problem[J]. Computers & Operations Research， 2009，36（1）：1639-1645.
[6] Fan W. Andrew L and Xu Z. The one-commodity pickup and delivery travelling salesman problem on a path or a tree[J]. Wiley Inter Science， 2006，48（1）：24-35.
[7] 赵方庚，李苏剑，刘伟民，等. 一类特殊的集送一体化TSP问题及其遗传算法求解[J]. 计算机工程与应用， 2009，45（2）：246
-248.
[8] Nenad M， Dragan U， Said H， et al. A general variable neighborhood search for the one-commodity pickup-and-delivery traveling salesman problem[J]. European Journal of Operational Research， 2012，220（1）：270-285.
[9] Fanggeng Z， Sujian L， Jiangsheng S. Genetic algorithm for the one-commodity pickup-and-delivery traveling salesman problem[J]. Computer & Industrials Engineering， 2009，56（4）：1642-1648.
[10] Francois L， Salazar-Gonzalez J. On the one-commodity pickup-and-delivery traveling salesman problem with stochastic demands[J]. Math. Program， 2009，119：169-194.
[11] 付慧琳，牟廉明，戴锡笠，等. 求解1-PDTSP问题的改进蚁群系统[J]. 内江师范学院学报，2013，28（10）：1671-1785.
[12] 牟廉明，戴锡笠. 求解选择性单商品配送收集问题的有效蚁群算法[J]. 计算机应用与软件，2013，30（12）：93-96.
关键词：运筹学；单商品旅行商问题；油耗；遗传算法
中图分类号：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的一个关于路径和树形拓扑结构的优化算法；2009年赵方庚等人[7]给出一个遗传算法来解决此问题；2012年Nenad Mladenovic等人设计了求解1-PDTSP的变邻域搜索算法[10]，这些启发式算法都能较好地解决大规模1-PDTSP，然而由于1-PDTSP只考虑优化车辆总的行驶费用，而在当今社会，随着能源的短缺和环境污染的日趋严重，油耗问题成为人们关注的焦点，因此本文研究带油耗的1
-PDTSP，该问题到目前为止还没有人研究过，它与1-PDTSP的区别在于既考虑车辆的行驶费用又考虑车辆的载货量产生的耗油费用，这样一来，虽然两个问题的可行集是相同的，但最优解不同，下面举例说明。
设有1个车场，4个客户点，它们的需求及相互之间的距离分别如下列的表1和表2所示，车辆容量为10。
设单位距离费用为1，单位距离单位重量费用为1.2，于是所有可行解及相应的费用如表3所示。
所以不考虑油耗和考虑油耗的最优解分别为：1→2→4→5→3→1和1→5→3→2→4→1，说明带油耗和不带油耗的1-PDTSP是有区别的，求解后者的算法不适用于前者，本文第3节的例子也说明了这一点，因此本文根据带油耗的1-PDTSP的特点设计了一个贪婪式启发式算法和一个遗传算法求解它，其中的遗传算法是将文献[7]的遗传算法进行修改得到的。
1 带油耗的1-PDTSP问题及其数学模型
（4）计算可行解1、可行解2对本文问题的目标函数值，将目标函数值最小的可行解存储在一个1行3列的元胞数组的第2个元素里，该元胞数组的第1个元素存储1，第3该元素存储该解对本文问题的目标函数值的倒数，得到一条染色体。重复使用该方法生成100条染色体得初始种群。
交叉：
采用GA_1的交叉方法，但要将在可行邻居中挑选下一客户点的规则改为在可行邻居中挑选需求绝对值除以到未完成路径中最后一个客户点的距离最大者为下一个客户点。
变异：
采用GA_1的变异方法。
3 例 子
在本例中，客户数为70，本文用文献[7]中的方法生成例子： 车场的坐标为0，0，其它70个客户点的横纵坐标在-500，500范围内随机生成，每个客户的需求q在-10，10范围内随机产生，车场需求车辆容量为10，单位重量单位距离的运输费用是1.5，空载时单位距离的行驶费用是1。表4为各客户点的需求量，图1为车场和所有客户点的位置图。
应用贪婪式启发式算法和本文的遗传算法GA_2得到的本例的次优解相同，都为哈密顿回路：
0→27→14→58→34→43→47→32→1→57→51→40→26→21→48→61→18→41→37→35→23→59→29→3→16→53→52→31→66→15→44→4→65→8→54→36→46→30→69→11→62→39→67→9→25→28→56→22→68→42→64→50→55→63→38→12→20→45→70→24→5→19→60→33→2→6→49→7→10→17→13→0 该解记为Solution_1，它对本文问题的目标函数值为：236950/3=7.898331178012094e+04。
应用文献[7]中的遗传算法GA_1得到的求解不带油耗的1-PDTSP问题的次优解（该解也是本文问题的可行解）为哈密顿回路：
0→65→21→48→61→18→41→23→59→37→22→30→69→11→67→9→36→8→54→42→64→60→33→4→32→43→14→27→47→58→57→44→15→52→53→16→31→66→63→55→40→51→34→45→20→50→12→26→38→49→7→3→35→56→28→39→62→2→68→46→25→19→5→70→1→24→17→29→13→6→10→0
该解记为Solution_2，它对本文问题的目标函数值为：323222/3=1.077406446095206e+05。
显然对本文的问题而言Solution_1的目标函数值要远远小于Solution_2的目标函数值，因此求解不带油耗的1-PDTSP的算法不适合求解本文的带油耗的1-PDTSP。
4 结 论
由于近年来对油耗问题的关注，本文针对过去的1-PDTSP，提出了带油耗的1-PDTSP，这更具有现实意义。根据本问题的特点给出了求解算法，并通过例子对算法进行说明，结果表明本文给出的算法适合用于求解带油耗的1-PDTSP。
参考文献：
[1] Hernández-Pérez H， Salazar-González J. The one-commodity pickup-and-delivery traveling salesman problem[J]. Combinatorial Optimization （Edmonds Festschrift）， 2003，2570：89-104.
[2] Hernández-Pérez H， Salazar-González J. A breach-and-cut algorithm for a traveling salesman problem with pickup and delivery[J]. Discrete Application Mathematics， 2004，145（1）：126-139.
[3] Hernández-Pérez H， Salazar-González J. Heuristics for the one-commodity pickup-and-delivery traveling salesman problem[J].Transportation Science， 2004，38（2）：245-255.
[4] Hernández-Pérez H and Salazar-González J. The one-commodity pickup-and-delivery traveling salesman problem Inequalities and algorithms[J]. Wiley Inter Science， 2007，50（4）：258-272.
[5] Hernández-Pérez H， Inmaculada M， Salazar-González J. A hybrid GRASP VND heuristic for the one-commodity pickup-and-delivery traveling salesman problem[J]. Computers & Operations Research， 2009，36（1）：1639-1645.
[6] Fan W. Andrew L and Xu Z. The one-commodity pickup and delivery travelling salesman problem on a path or a tree[J]. Wiley Inter Science， 2006，48（1）：24-35.
[7] 赵方庚，李苏剑，刘伟民，等. 一类特殊的集送一体化TSP问题及其遗传算法求解[J]. 计算机工程与应用， 2009，45（2）：246
-248.
[8] Nenad M， Dragan U， Said H， et al. A general variable neighborhood search for the one-commodity pickup-and-delivery traveling salesman problem[J]. European Journal of Operational Research， 2012，220（1）：270-285.
[9] Fanggeng Z， Sujian L， Jiangsheng S. Genetic algorithm for the one-commodity pickup-and-delivery traveling salesman problem[J]. Computer & Industrials Engineering， 2009，56（4）：1642-1648.
[10] Francois L， Salazar-Gonzalez J. On the one-commodity pickup-and-delivery traveling salesman problem with stochastic demands[J]. Math. Program， 2009，119：169-194.
[11] 付慧琳，牟廉明，戴锡笠，等. 求解1-PDTSP问题的改进蚁群系统[J]. 内江师范学院学报，2013，28（10）：1671-1785.
[12] 牟廉明，戴锡笠. 求解选择性单商品配送收集问题的有效蚁群算法[J]. 计算机应用与软件，2013，30（12）：93-96.