2010西工大数模竞赛B题论文

摘   要

随着网购的盛行，物流行业也渐渐兴盛。为了达到送货员以最快速度及时将货物送达的目的，本文针对所给线路及送货要求的最佳线路设计问题展开研究，利用图论、整数规划模型分别对各问题求解：

对问题一，先由算法求得任意两地点间的最短距离。模型一建立问题图论模型，找到增广完全图的回路作为精确最优解，并由此求得最短路程为米，最快用时。模型二，第一步，只针对前30号货物送达地点构成的网络图（含14个奇点），利用中国邮路问题的图论模型，找出欧拉回路即为最快送货路线；第二步，通过加入临近点和去边的方式优化第一步所建模型，得到奇点最少的网络图（含4个奇点），并将由此得到的欧拉回路作为最快送货路线。

对问题二，由于加入时间约束的问题属于难问题，此处将所有送达时间相同的点视为等目标点分在一个点集，则本问中的点可分为4个点集，按时间先后顺序遍历各点集，再用问题一的模型找出的回路作为一个近似最优解。到达最后一个送货地点并完成货物交接的时间是11点30分。

对问题三，我们采用了“选点分包-局部优化”的算法，将对题中所给的散点分成符合题中约束的三组；对每组散点，利用问题一中已有的算法，求出各组送货地点的回路，即得所求最优解的一个可能值，经过对分组方法的四次逐步改进，得到一个较为合理的优化结果，送完所有货物的最快时间657.842分钟。

最后本文还结合实际情况，对模型的优缺点进行了分析与评价，并提出了改进方向。

关键词：回路  欧拉回路  等目标点集  选点分包-局部优化

目录

1.    问题重述    2

1.1.    问题背景    3

1.2.    实际现状    3

1.3.    问题提出    3

2.    基本假设    4

3.    符号说明及名词解释    4

3.1.    基本符号    4

3.2.    部分名词解释    4

4.    模型建立    4

4.1.    问题一    5

4.1.1    问题分析    5

4.1.2    模型建立    7

4.2.    问题二    11

4.2.1    问题分析    11

4.2.2    模型建立    11

4.3.    问题三    12

4.3.1    问题分析    12

4.3.2    模型建立    12

5.    模型求解    15

5.1.    问题一    15

5.1.1    模型一    15

5.1.2    模型二    16

5.2.    问题二    17

5.3.    问题三    18

6.    结果表示、分析    19

6.1.    问题一    19

6.1.1    模型一    20

6.1.2    模型二    21

6.2.    问题二    22

6.3.    问题三    23

7.    模型的评价和推广    24

8.    参考文献    24

4.    附件清单    25

1.问题重述

1.1.问题背景

随着互联网的普及，作为购物新时尚的网购以其便捷、多样越来越受到人们的追捧，随之而来的货物配送问题也逐渐引起关注。

对物流公司而言，如何指定货物配送方案、选择最佳送货路线，不仅与公司运行成本息息相关，还关系到客户能否及时拿到货物从而影响企业信誉和竞争力。寻找最短送货路线、及时送达货物、怎样从物流中心分发货物都是需要考虑的因素。对顾客而言则更多关心货物能否以最快速度送达。

基于上述情况，根据题目所给数据，运用数学建模方法，对送货路线进行选择是一个重要问题。制定出合理的送货路线，使得最大限度的降低物流公司成本的同时最大限度的满足各个客户的需求对物流行业和网络购物的发展等诸多方面都有重要意义。

1.2.实际现状

对最佳送货路线的制定有以下几个特点：

1）物流公司考虑自身利益，追求送货路线最短；

2）根据客户需求，货物的送达有时间截点；

3）考虑运送能力，物流中心需要对全部货物进行合理分配；

……

这些因素都影响着最佳送货路线的制订。

1.3.问题提出

从一个快递公司的实际情况和上述特点出发，依据相关数据：

1．若由一个送货员将1~30号货物送到指定地点并返回，设计最快完成路线与方式，给出结果并标出送货线路。

2. 假定该送货员从早上8点上班开始送货，要将1~30号货物在指定时间前送达目的地，请设计完成任务的最短路线。要求标出送货线路。

3. 若不需要考虑所有货物送达时间(包括前30件货物)，现在要将100件货物   分次全部送到指定的50个地点并返回，设计完成任务的最短路线。并标出送货线路，给出送完所有快件的时间。由于受重量和体积，送货员可中途返回取货，不考虑中午休息时间。

2.基本假设

1、假设送货员速度恒定、货物交接时间恒定，不受自然因素和突发事件影响 ；

2、假设送货员在某点停留一次进行货物交接以后, 该送货员以后通过这里不再停留, 直接通过；

3、假设找到最佳路线后送货员一定沿着最佳路线走，而不会选择其他路线；

4、送货员在送货过程中, 路途畅通, 无任何延误时间；

5、送货员对道路情况很了解，不会在多支路的点处选择错误路线；

3.符号说明及名词解释

3.1.基本符号

等目标点：所有目标送达时间相同的点。

4.模型建立

4.1.问题一

1

2

3

4

4.1

4.1.1问题分析

该问题给出了某城市的路线网络示意图，在①送货员走遍1~30号货物所指定的21个送货地点，又回到库房的过程中速度、货物交接时间恒定，②1~30号货物的总质量、总体积的前提下，我们所关心的问题是：如何设计出合理的送货路线的优化方案，使送货总路线的总路程最短，即为最快完成路线与方式。

4.1.1.1模型一

通过分析走遍1~30号货物所指定的22个送货地点又回到库房的要求，我们发现，这与TSP问题的回路联系最为密切，于是考虑用现有的Hamilton回路的一些研究成果以及相关的图论、运筹学知识来建立该问题的数学模型。

我们先引人回路的定义：

定义  在网络图中, 从某一顶点出发, 过每个顶点一次且只经过一次并回到原出发顶点, 则该回路称为回路, 简称H-回路。

在巡回送货路线中, 由假设2我们可把已停留过一次进行货物交接的地点近似地视为路段, 送货员再次到该地点时以正常速度通过, 不再停留, 从这个意义上讲, 它符合H-回路的定义, 但由于该城市道路网络图本身不是一个完全图, 不能在上面直接求出最优H-回路, 因此, 要通过适当的加工处理, 使其转化为一个标准的增广完全图为此, 我们引人下面的定理：

定理  在网络图中, 任意两个顶点若都能满足下述不等式, 则该网络图与H-回路等价。其中表示顶点与顶点之间的距离（或路程）。

据此, 我们可得到把城市道路网络图化为增广完全图的方法如下：如果图（这里表示巡回路线图的某个局部）不满足上述不等式, 那么就用从到的最短路去替换使不等式不成立的那些弧长即可。从到的最短路可以利用算法求出。

求H-回路时，我们先建立混合整数线性规划模型，找到遍历所有送货地点后返回库房的最短路线（即遍历各点的先后顺序）；然后，用两点间的最短最短路去替换使不等式不成立的那些弧长即可。

对模型一的求解过程如下：

Floyd算法

求任意两点间的最短距离

混合整数线性规划

确定H-回路

对不能直接连通的两点进行修正

确定距离最短的送货路线

4.1.1.2模型二

由走遍1~30号货物的指定送货地点又回到库房的要求，我们发现，这与中国邮路问题联系亦很密切，于是考虑用现有的中国邮路问题的一些研究成果以及相关的图论、运筹学知识来建立该问题的数学模型。

我们首先引入中国邮路问题的描述：

给定一个连通图，每边都有非负权，要求经过每边至少一次，且满足总权最小。对于没有奇点的中国邮路问题，图的任一条回路即为满足条件的路线（为可行回路），对于存在奇点的中国邮路问题，有些边必需重复至少一次才能找到一条可行回路。

据此，我们第一步，在模型一用算法求出任意两点间最短距离的基础上，利用中国邮路问题的图论模型（含14个奇点），找出欧拉回路作为局部最优解，发现总路程大于60000米，与模型一结果比较发现该基础模型需要改进；第二步，通过加入临近点和去边的方式优化第一步所建模型，得到奇点最少的网络图（仅含4个奇点），并将由此得到的欧拉回路作为最快送货路线。

对模型二的求解过程如下：

用0-1规划对奇点进行配对

找到欧拉回路

Floyd算法

求任意两点间的最短距离

添加临近点、去掉可以使奇点数减少的边，并重复第二步

确定距离最短的欧拉回路

4.1.2模型建立

4.1.2.1模型一

1-30号货物送货地点图

从原始区域集（即所有指定地点组成的集合）中取1~30号货物送达的指定地点及为了增强网络图的连通性引入的点（19、35号点）组成目标点集，分别标号为1,2,3，…，23，库房标号为24。通过算法求解出任意一点到另外一点的最短距离，从而将它作为混合整数线性规划中目标函数的权值（关于算法，将会在模型的求解过程给与详细论述）。

设送达地点之间最短距离用矩阵表示，表示地点与地点之间的距离。设0-1矩阵表示经过的各地点之间的路线。设

考虑每个地点前只有一个地点，则

考虑每个地点后只有一个地点，则：

但仅以上约束条件不能避免在一次遍历中产生多于一个互不连通回路。为此我们引入额外变量，附加以下充分约束条件：     ；其中。

    该约束的解释：

如与不会构成回路，若构成回路，有：，，则：

，，从而有：    ，导致矛盾。

如，与不会构成回路，若构成回路，有：，，则：

，，从而有：，导致矛盾。

其它情况以此类推。

于是我们可以得到如下的混合整数线性规划模型，记为所走路线距离总和：

4.1.2.2模型二

1）基础模型

i.在模型一已求得任意两点间最短距离的基础上，引入中国邮路问题的图论模型。

ii.找奇点间的最优配对关系，加入重复边，使原网络图转化为连通图

设变量表示顶点和的配对关系

为网络中重复边的总和，为奇点总数（此处），得到0-1规划模型：

此模型用到的假设：假设只考虑送货地点及库房而不考虑临近点构成的网络图

iii.找到欧拉回路即为该模型下能够遍历所有点最后回到出发点的最短路线

2）改进模型

由中国邮路问题模型算法，并结合本问网络图可知：

i.欲使非欧拉图转化为欧拉图需要在找出的最优配对奇点间加入重复边，奇点数越多加入的重复边总和越大，得到的欧拉回路越长；

ii.引入临近点可以减少2个奇点，且可增强图的连通性；

iii.去掉两奇点间的边可以减少奇点数目，如去掉间的边；

iv.去掉与度数大于3的奇点相连的边而不影响图的连通性可以减少奇点数目，如去掉间的边，并由此得出去掉、、间的边；

v.去掉、间的边亦可减少奇点数目

模型改进过程如下图所示：                 表示需要去掉的边

                                         表示网络图中其他剩余的边

图4.1.2.2.1  改进后的网络图

经过以上步骤可以将奇点数由原来的14个减少为4个，并且可以证明奇点数目不可能再减少，由此得到奇点数目最少的网络图。步骤二、三同基础模型。

4.2.问题二

4.2

4.2.1问题分析

在问题一的基础上，考虑1~30号货物的送达时间，即在满足时间条件下，求一路径使该路径耗时最少。将所有目标送达时间相同的点分在一个点集，则本问中的点可分为4个点集，在图中找出这四个点集的分布，发现属于同一点集的点分布区域相近。

由此，我们考虑按送达时间先后顺序遍历这四个点集，再对每个点集中的点找到满足时间约束的最短路线。寻找最短路线的方法可以用问题一中模型一的回路。

4.2.2模型建立

1)本问在问题一的基础上加入时间约束，即在满足的条件下，求一路径使该路径耗时最少。

时间约束：    

到达第点所需时间：     

对以上模型的参数解释：

——1~30号货物涉及到时间约束的一个排列；

——给定时间上界，本题中

——第个送货地点需要交接的货物数量；

——库房至送货地点的路程距离和；

2)问题一中已经求得使最短的回路，考虑到加入时间约束后该TSP问题成为难问题，且本问中目标点数目较小，故可从问题一找到的结果中引入修正，有望得到近似最优解。

4.3.问题三

4.3

4.3.1问题分析

本问要求将100件货物全部送到指定地点并返回，考虑到100件货物质量总和，超过了送货员单次最大载重50公斤、货物最大体积1立方米，所以需要以最大载重和货物最大体积为约束条件，将货物送达目的地进行分区（至少分为三个区），再用问题一的模型一逐一找出每个区的回路。

4.3.2模型建立

本问描述：由一个送货员从仓库到达城市内多个地点送货。每个地点的位置和货物的需求量一定，送货员单次最大载重、货物最大体积一定。要求合理设计最快完成路线与方式。并满足下列条件：（1）每次配送各地点的客户需求量之和不超过送货员单次最大载重、货物最大体积；（2）每个地点的客户需求必须满足，且只能由送货员在一次送货过程中送达。

N 表示送货地点的数目，地点标号从1 到50，标号51 表示库房O；表示送货员单次最大载重50公斤， 表示货物最大体积1立方米；表示各地点的客户需求量； 表示为从点到的最短距离。

本问数学模型如下：

本问属典型的多旅行商问题，理论上已证明在多项式时间内该题不可解,所以属于NP难问题。针对此类问题，目前存在遗传，神经网络，扫描法等多种算法，均是获得近似最优解的有效算法，对于本题来说，通过MATLAB图像分析可知，散点的分布具有一定的聚集性，故尝试采用选点分包的方式，尝试获得较为合理的最优解。

重量按颜色的分布

图4.3.2.1

体积按颜色的分布

图4.3.2.2

图4.3.2.3

为了找到本问的近似最优分组我们建立如下分组原则：

1）每组货物的质量、体积和尽可能平均分配；

2）每组货物的送达地点尽可能集中；

3）根据所有货物质量、体积总和与质量、体积约束的关系分为3组；

5.模型求解

5.1.问题一

5

5.1

5.1.1模型一

1）根据给出的各点位置坐标及相互到达信息，用MATLAB编程求解各点之间的距离，用算法得到任意两点间的最短距离（算法源程序见附件1）

上述解法中的算法用于求任意两点间的最短距离，其程序流程如下：（注： 到的距离； 到之间的插入点．）

i.输入: 带权邻接矩阵;

ii.赋初值：对所有 1;

iii.更新，：对，若，则)+,;

iv.若，停止．否则，转(3)．

2）利用Lingo软件，通过该混合整数线性规划模型，可找到遍历所有送货地点后返回库房的H-回路， 24-10-7-4-2-3-8-13-15-16-17-21-20-23-22-19-14-18-11-12-9-6-1-5-24   对应H-回路  

该步用到的近似：将第一步得到的各点之间的最短距离四舍五入取整数代入Lingo程序（因为任意两点间最短距离在数量级以上，取整数不会影响到程序运行结果）

（Lingo程序见附件2）

3）根据各点间相互到达信息知、、间没有直接通路，不符合完全图条件；用第一步得到的从到的最短路径(程序源代码见附件3)去替换使不等式不成立的那些弧长，使原网络图转化为增广完全图，得到最短路线为

表示送货员在某点停留一次进行货物交接以后, 该送货员以后通过这里就不再停留, 直接通过；总路程54708米，用时3小时46分钟。

5.1.2模型二

1）基础模型

i.直接使用模型一得到的任意两点间最短距离作为边的非负权；

ii.利用lingo软件，求解0-1规划模型，可找到14个奇点间的配对关系如下：

目标函数添加重复边总和最小值；

iii.由于中国邮路问题要求每边（包括重复边）至少走一次，得到总路程大于60000米，与模型一得到的结果比较知，没有经过改进的中国邮路问题模型并不适用于该问题，于是考虑对模型进行改进。

2）改进模型

i.在基础模型上通过加入临近点和去边的方式得到含奇点数目最少的网络图，加点、去边的具体方式如下：加入临近点，去掉、、、、、、间的边。分析过程见模型建立部分。

ii.重复上述模型求解过程第二步，找到4个奇点间配对关系如下（见下页图）：，目标函数最小值

iii.在邮路图中对每个配对奇点之间按照最短路径添加重复边，得到，不含奇点

iv.从库房出发，找出欧拉回路，此回路即为送货员的最短路线，总路程为54870米。

5.2.问题二

1)按将22个送货地点分为4个点集，其中定义相同的点为等目标点。

观察中各点，除（）外，其余等目标点相连（如：），故此问中各点均应依次通过（从绕过上述），依次检查等目标点中距原点路程最远点的达到时间：      

计算过程如下表：

对等目标点集合，为了利用问题一的方法，考虑从回的情形。假设将，相连并取，用问题一中模型一的方法得到的回路作为近似最优解，同理考虑点集中其余各点回到的情况，得到其余点回的近似最优解，取=  即为本问的最优解。

5.3.问题三

根据我们建立的分组原则，通过Excle对所有货物质量、体积数据进行统计处理，找到3组分组方法，其中最优分组方法为

分组路径为：

6.结果表示、分析

6.1.问题一

6

6.1

6.1.1模型一

6.1.1.1结果表示

根据基本假设1，最短送货路线即为最快送货路线，如下图所示：

图6.1.1.1.1   H-回路最快送货路线图

最短送货路线总路程为54708米，最快用时3小时46分钟。

6.1.1.2结果分析

该模型根据本问特点联系Hamilton回路问题，又巧妙的利用算法求出的任意两点间最小距离将网络图转化为增广完备图，从而找到遍历所有送货地点最后回到库房的H-回路作为最快送货路线。本问由于没有其他约束条件（如时间、体积、质量），可以得到精确最优解。

6.1.2模型二

6.1.2.1结果表示

由经过改进的模型得到欧拉回路即为最快送货路线，如下图所示：

图6.1.2.1.1  欧拉回路最快送货路线图

6.1.2.2结果分析

该模型联系中国邮路问题，引入欧拉回路作为最快送货路线。并根据找到欧拉回路的算法思想，提出通过加入临近点、去边的方式减少奇点数目，从而减少添加重复边，得到目标函数重复边距离总和的最小值。该模型的进一步分析将在模型的评价和推广中给出。

6.2.问题二

6.2

6.2.1结果表示

找到的满足时间约束的最短送货路线如下图所示：

到达最后一个送货地点并完成货物交接后的时间是11点30分

图6.2.1.1 近似最短送货路线图

6.2.2结果分析

本问在问题一的基础上引入时间约束，使该问题成为难问题，为了找到近似最优解，采用上述近似算法并结合问题一的回路方法，得到满足送货时间约束条件的近似最快送货路线。

6.3.问题三

6.3

6.3.1结果表示

找到的近似最优分组路线如下图所示：

图6.3.1.1

分组路径为：

6.3.2 结果分析

本问属典型的多路旅行商问题，理论上已证明在多项式时间内该题不可解,所以属于NP难问题。对于本问来说，通过MATLAB图像分析可知，散点的分布具有一定的聚集性，故尝试采用选点分包的方式，尝试获得较为合理的最优解，并据此提出了分组原则，找到一个近似最优解。

7.模型的评价和推广

1、问题一中，模型一联系回路问题得到精确最优解的前提是：1~30号货物的总质量、总体积，又无需考虑时间约束。而事实上，回路问题属于难问题，也就是说,，当问题含有其他约束条件时,，要想求得真正的最优解是不现实的，为此， 必需采取灵活多样的方式和方法, 求近似得最优解。

2、问题一中，模型二联系中国邮路问题找出欧拉回路作为该问题的近似最优解。基础模型中由于奇点数目很多加入的重复边距离总和大，得到的解与模型一得到的精确最优解相差很大，但这并不意味着该问题不能由中国邮路问题模型求解。于是我们提出改进模型，其核心思想是通过加点、去边的方式使奇点数减少（之所以这样做是因为本问并不像中国邮路问题那样要求经过每边至少一次）。通过改进模型我们发现类似本问的问题不仅可以用回路找到精确最优解，还可以用改进后的欧拉回路求解。

3、问题二在问题一的基础上引入时间约束，使之成为难问题，无法找到精确最优解。本问题中的算法都只是近似算法, 所得最佳路线也只是近似最优解。

4、问题三属典型的多路旅行商问题，理论上已证明在多项式时间内该题不可解,所以属于NP难问题。对于本问来说，通过MATLAB图像分析可知，散点的分布具有一定的聚集性，故尝试采用选点分包的方式，尝试获得较为合理的最优解，并据此提出了分组原则，找到一个近似最优解，具有一定创新性。

5、问题三对约束条件的求解只是概括地分析, 没有给出具体的算法。

6、由于本题采用图论模型与整数规划模型相结合的方法求解,并提出能够找到该NP难问题的近似算法或原则，可以较好的推广到解决灾情巡视线路、投递、旅行商等实际问题。

8.参考文献

1.张志涌等，、MARLAB教程，北京航空航天大学出版社，2009年修订；

2.黄雍检等，MARLAB语言在运筹学中的应用，河南大学出版社，2005；

3.胡玖平等，运筹学（第二版），科学出版社，2004；

4.附件清单

1.附件1：算法求解任意两点间的最短距离源程序；

2.附件2：问题一中模型一Lingo程序源代码； 

3.附件3：任意两点间最短路径源程序； 

附件1：算法求解任意两点间的最短距离程序

function y=fld(n,x)

for r=1:n

    for i=1:n

        for j=1:n

            p(j)=x(i,j)+x(j,r);

        end

        y(r,i)=min(p);

    end

end

end

24个点之间的

x=[9185

1445

……

8010

11000]';

y=[500

560

……

15325

8250]';

dx=ones(51);

for i=1:51

    for j=1:51

        dx(i,j)=x(i)-x(j);

    end

end

dy=ones(51);

for i=1:51

    for j=1:51

        dy(i,j)=y(i)-y(j);

    end

end

d0=ones(51);

for i=1:51

    for j=1:51

        d0(i,j)=sqrt(dx(i,j).^2+dy(i,j).^2);

    end

end

commute=[1  3

1   8

2   20

……

49  42

50  40

51  18

51  21

51  26];

 d=ones(51);d=d*inf;

 for i=1:51

    d(i,i)=0;

end

for i=1:83

    m=commute(i,1);n=commute(i,2);

    d(m,n)=d0(m,n);

    d(n,m)=d0(n,m);

end

c=[13 14 16 17 18 19 21 23 24 26 27 31 32 34 35 36 38 39 40 42 43 45 49 51];

d24o=ones(24);

for i=1:24

    for j=1:24

        d24o(i,j)=d(c(i),c(j));

    end

end

function y2=fd(n,k,w)

for i=1:k

    d=fld(n,w);

    w=d;

end

end

k=round(log(n-1)/log(2));

d244=fd(24,4,d24o);

 dmin=d0(51,26)+d0(26,21)+d0(21,17)+d0(17,14)+d0(14,16)+d0(16,23)+d0(23,32)+d0(32,35)+d0(35,38)+2*d0(36,38)+d0(38,43)+d0(43,42)+2*d0(42,49)+d0(42,45)+d0(45,40)+d0(40,34)+d0(34,31)+2*d0(31,27)+2*d0(27,39)+d0(31,24)+d0(24,19)+d0(19,13)+d0(13,18)+d0(18,51);

附件2：问题一模型一Lingo程序源代码

TSP quesion;

MODEL:

SETS:

point/1..24/:u;

link(point,point):d,x;

ENDSETS

DATA:

d= 0    8456    11063    16    3113    3456    7092    10691    5714    6688    6285    5217    12003    7542    11436    84    10026    8065    9173    13562    125    11671    15534    5295

8456    0    2608    2196    5342    110    3297    3970    8806    5488    8093    7025    5282    9350    6396    6177    7714    9873    10981    11250    10333    9359    13222    5094

11063    2608    0    3872    7950    134    5696    2098    11205    7888    9675    9425    3410    11750    4524    7471    5933    11454    13380    9469    8552    10653    11441    7493

16    2196    3872    0    5803    9591    1824    1775    7333    4016    6620    5553    3086    7877    4200    4704    5610    8400    9508    9146    8229    7887    11118    3621

3113    5342    7950    5803    0    6142    3979    7577    3884    3574    3171    2104    88    4428    8323    5375    6913    4951    6059    10449    9531    8558    12420    2182

3456    110    134    9591    6142    0    7768    11366    2259    5576    5107    4039    11372    63    10258    7310    8848    6886    7994    12384    11466    10493    14355    6968

7092    3297    5696    1824    3979    7768    0    3598    5509    2192    4797    3729    4910    6054    5827    2880    4418    6576    7684    7954    7036    6063    9925    1797

10691    3970    2098    1775    7577    11366    3598    0    9107    5790    7577    7327    1312    9652    2426    5373    3836    9357    11283    7372    54    8555    9343    5395

5714    8806    11205    7333    3884    2259    5509    9107    0    3317    2848    1780    9113    4105    7999    5052    65    4628    5736    10125    9208    8234    12097    4709

6688    5488    7888    4016    3574    5576    2192    5790    3317    0    2605    1537    7102    3862    7756    4809    6346    4385    5493    9882    65    7991    11854    1392

6285    8093    9675    6620    3171    5107    4797    7577    2848    2605    0    1068    6265    3393    5151    2204    3741    1780    5023    7277    6360    5386    9249    3997

5217    7025    9425    5553    2104    4039    3729    7327    1780    1537    1068    0    7333    2325    6219    3272    4809    2848    3956    8345    7428    54    10317    2929

12003    5282    3410    3086    88    11372    4910    1312    9113    7102    6265    7333    0    9658    1114    4061    2524    8045    10461    6060    5142    7244    8031    6707

7542    9350    11750    7877    4428    63    6054    9652    4105    3862    3393    2325    9658    0    8544    5596    7134    5172    1631    7200    8117    4848    9171    5254

11436    6396    4524    4200    8323    10258    5827    2426    7999    7756    5151    6219    1114    8544    0    2947    1410    6931    9347    4946    4028    6130    6917    7624

84    6177    7471    4704    5375    7310    2880    5373    5052    4809    2204    3272    4061    5596    2947    0    1537    3984    6399    5074    4156    3182    7045    4677

10026    7714    5933    5610    6913    8848    4418    3836    65    6346    3741    4809    2524    7134    1410    1537    0    5521    7937    3536    2618    4720    5507    6215

8065    9873    11454    8400    4951    6886    6576    9357    4628    4385    1780    2848    8045    5172    6931    3984    5521    0    6803    9057    8140    7166    11029    5777

9173    10981    13380    9508    6059    7994    7684    11283    5736    5493    5023    3956    10461    1631    9347    6399    7937    6803    0    5569    86    3217    7540    6885

13562    11250    9469    9146    10449    12384    7954    7372    10125    9882    7277    8345    6060    7200    4946    5074    3536    9057    5569    0    918    2352    1971    9751

125    10333    8552    8229    9531    11466    7036    54    9208    65    6360    7428    5142    8117    4028    4156    2618    8140    86    918    0    3269    28    8833

11671    9359    10653    7887    8558    10493    6063    8555    8234    7991    5386    54    7244    4848    6130    3182    4720    7166    3217    2352    3269    0    4323    7860

15534    13222    11441    11118    12420    14355    9925    9343    12097    11854    9249    10317    8031    9171    6917    7045    5507    11029    7540    1971    28    4323    0    11722

5295    5094    7493    3621    2182    6968    1797    5395    4709    1392    3997    2929    6707    5254    7624    4677    6215    5777    6885    9751    8833    7860    11722    0

;

!只输出为x(i,j)=1的值;

@text()=@writefor(link(i,j)|x(i,j)#GT#0:'x(',i,',',j,')=',x(i,j),' ');

ENDDATA

  MIN=@SUM(link:d*x);

    n=@size(point);

  @for(point(j):@sum(point(i)|j#ne#i:x(i,j))=1); !点j前有一个点相连;

  @for(point(i):@sum(point(j)|j#ne#i:x(i,j))=1); !点i后前有一个点相连;

  @for(link(i,j)|i#NE#j#and#i#gt#1:u(i)-u(j)+n*x(i,j)<=n-1);

@FOR(link:@BIN(x));

end

附件3：任意两点间最短路径源程序

function  [ci,cj,v,dij]=stlin(n,i,j,d)

ci=d(i,j)-d(i,:);

cj=d(:,j)';

v=zeros(1,n);

dij=d(i,j);

for m=1:n

    if abs(ci(m)-cj(m))<10

        v(m)=m;

    end    

end

!TSP quesion;

MODEL:

SETS:

point/1..11/:u;

link(point,point):d,x;

ENDSETS

DATA:

d= !输入距离矩阵;;

!只输出为x(i,j)=1的值;

@text()=@writefor(link(i,j)|x(i,j)#GT#0:'x(',i,',',j,')=',x(i,j),' ');

ENDDATA

  MIN=@SUM(link:d*x);

    n=@size(point);

  @for(point(j):@sum(point(i)|j#ne#i:x(i,j))=1); !点j前有一个点相连;

  @for(point(i):@sum(point(j)|j#ne#i:x(i,j))=1); !点i后前有一个点相连;

  @for(link(i,j)|i#NE#j#and#i#gt#1:u(i)-u(j)+n*x(i,j)<=n-1);

@FOR(link:@BIN(x));

end