快递公司送货策略数模论文

1、承诺书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则 我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮 件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问 题。矚慫润厲钐瘗睞枥庑赖。我们知道，抄袭别人的成果是违反竞赛规则的，如果引用别人的成果或其他 公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正 文引用处和参考文献中明确列出。聞創沟燴鐺險爱氇谴净。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反 竞赛规则的行为，我们将受到严肃处理。残骛楼諍锩瀨濟溆塹籟。我们参赛选择的题号是（从 A/B/C中选择一项填写）： C我们

2、的参赛报名号为（如果赛区设置报名号的话）： 所属学院（请填写完整的全名）：自动化参赛队员（打印并签名）：1.2.3日期：2013 年月23 日评阅编- 号（教师评阅时填写）：6快递公司送货策略摘要：本文是关于如何优化快递公司送货策略的问题，即在给定送货地点和 给定设计规范的条件下，确定所需业务员人数，每个业务员的运行线路，总的运 行公里数，以及费用最省的策略。本文主要从最短路经和费用最省两个角度解决该问题。酽锕极額閉镇桧猪訣锥。针对问题一，利用单目标0-1规划模型和最佳匹配的原理，将送货点抽象为 顶点，由于街道和坐标轴平行，即任意两顶点之间都有路。在此模型中，将两点 之间的距离为这两点横纵坐标

3、差的绝对值之和。比如A（x1, y1），B（x2, y2）两点，则两点之间距离为d=|x2-x1|+|y2-y1|。通过多目标动态规划找出初步路径，再通过lingo软件对各路径进行优化。通过分析，其模型结果为：共需要 5 名快递员。快递员1： 0-29-28-30-23-15-0;快递员2： 0-8-26-27-0 ;快递员3： 0-19-24-25-0-1-6-5-2-0;快递员 4: 0-16-17-18-20-0-3-7-4-0;快递员 5：0-9-11-21-22-10-0-12-13-14-0 路程为461km 所需总的时间为23.44h。彈贸摄尔 霁毙攬砖卤庑。针对问题二，根据题意

4、，建立单目标0-1整数规划的数学模型，然后用类似 于问题一的方法，建立满足题意的目标函数以及约束条件，并求得最优结果。最后，对所求解的方案进行修改。所得结果为：快递员1走0-1-3-8-13-0-25-26-0；快递员2走0-2-4-7-14-0 ;快递员 3走：0-6-5-20-18-30 ;快递员 4走： 0-10-11-21-23-0 ;快递员 5 走：0-16-17-24-28 ;快递员 6 走：0-22-29-0 ;快 递员7走：0-9-12-19-0-15-27-0;所走路程为616km,最少费用为13830.7元。謀养抟箧飆鐸怼类蒋薔。针对问题三，在问题二的模型基础上，改变时间的

5、条件约束，因为所需要的 总时间不变，而每个业务员的工作时间增加为8小时，所以对其工作量重新进行安排，得到结果为：需要4个快递员，快递员1走：0-6-5-20-18-30-0-15-27-0;快递员 2 走：0-16-17-24-28-0-25-26;快递员 3 走：0-10-11-21-23-0-0-22-29-0;快递员4 走: 0-1-3-8-13-0-2-4-7-14-0-9-12-19-0;厦礴恳蹒骈時盡继價骚。最后对论文所建模型进行了评价与推广。关键词：快递公司送货最优化分区送货策略模型TSP模型一、问题重述1.1问题背景：目前，快递行业正蓬勃发展，为我们的生活带来更多方便。一般地，

6、所有快 件到达某地后，先集中存放在总部，然后由业务员分别进行派送；对于快递公司， 为了保证快件能够在指定的时间内送达目的地，必须有足够的业务员进行送货， 但是，太多的业务员意味着更多的派送费用。茕桢广鳓鯡选块网羈泪。1.2问题提出：假定所有快件在早上7点钟到达，早上9点钟开始派送，要求于当天17点 之前必须派送完毕，每个业务员每天平均工作时间不超过 6小时，在每个送货点 停留的时间为10分钟，途中速度为25km/h,每次出发最多能带25千克的重量。 为了计算方便，我们将快件一律用重量来衡量，平均每天收到总重量为184.5千克，公司总部位于坐标原点处（如图2），每个送货点的位置和快件重量见下表，

7、 并且假设送货运行路线均为平行于坐标轴的折线。鹅娅尽損鹤惨歷茏鴛賴。图一送货点快件量T坐标（km）送货点快件量T坐标（km）xyXy1832163.521628.215175.86183654187.5111745.547197.815126308153.419954.5311326.222577.279226.821082.396232.427991.4102247.61519106.5140259.61514114.1173261020171212.714627122113135.8129286.02420143.81012298.12516204.6714304.22818（1）请你运用

8、有关数学建模的知识，给该公司提供一个合理的送货策略（即需要多少业务员，每个业务员的运行线路，以及总的运行公里数）；籟丛妈羥为贍债蛏练淨。（2） 如果业务员携带快件时的速度是 20km/h，获得酬金3元/km kg；而不携带 快件时的速度是30km/h，酬金2元/km，请为公司设计一个费用最省的策略； 預 頌圣鉉儐歲龈讶骅籴。（3）如果可以延长业务员的工作时间到 8小时，公司的送货策略将有何变化？y20 -1510| I x510152025二、基本假设（1）假设送货运行路线均为平行于坐标轴的折线（2）无塞车现象，即业务员送快递途中不受任何外界因素影响，且业务员的休息时间不包括在最大工作时间 6

9、个小时内。渗釤呛俨匀谔鱉调硯錦。（3）假设在问题一中若其中一个业务员跑多条路线时，中间返回总部后取快（将快件装上车）所花费的时间不计 在问题一中假设空载时的速度和有货物时的速度是相同的都是25km/h（5）每个业务员送快递是独立的，每人之间互不影响。（6）不走冤枉路原则（即送货时只能向上或者向右走）。三、符号说明符号说明单位W- IJ1,在第I条路线上业务员向第j个送货点送快件 0,在第I条路线上业务员不向第j个送货点送快件pij第I条路线上第j个送货点是最远点 0,第I条路线上第j个送货点不是最远点aj第j个送货点的所需的快件重量kg(jx, jy)表示第j个送货点的坐标t1业务员携带快件时

10、，按第i条路线派送快件所需时间ht2业务员不携带快件时，按第i条路线派送快件所需时间ht业务员按第i条路线所花费的总时间hN业务员送货的总次数四、问题分析问题要求给出快递公司送货的策略，要求我们根据不同情况和要求为快递公 司提供合理的送货策略，题中给出了实际送货点的位置和快件重量表， 并且抽象 到一个平面的二维坐标系中，题中假设送货运行路线均为平行于坐标轴的折线， 则我们可以用平行于坐标轴的折线连接两个送货点，它们之间的距离为两坐标差的绝对值D = xXj + % -yj .题中还给出了几个已知条件和限制条件：铙誅卧泻 噦圣骋贶頂廡。1. 每个业务员平均工作时间不超过 6小时;2. 在每个送货

11、点停留的时间为10分钟；3. 途中速度为25km/h5.每次出发时带的重量不超过25kg ；4. 平均每天收到的货物总重量为184.5kg送货问题的难点在于当运输能力和送货点一定的情况下，如何选择最优的送 货路线，而最优的目标有多个：送货总路程最短，运输时间最短，所需业务员人数 最少或运输成本最低。在大多数情况下，由于送货总路程与运输时间正相关与运输成本负相关。因此，为了便于叙述和推导，我们直接选取送货总路程最短和 所需业务员最少作为我们优化送货线路的最终目标.由题意可知，平均每天收到总重量为184.5千克，每个人的最大负重是25kg，即型占=7.38,则可知至少需25要8条路线对这些邮件进行

12、运送。 擁締凤袜备訊顎轮烂蔷。对于问题一的要求，给该公司提供一个合理的送货策略。其中所谓“合理”， 我们可以理解为业务员尽量少，每个业务员的运行路线尽量短，完成任务的时间 尽量短。再以这个要求为原则进行方案设计。 贓熱俣阃歲匱阊邺镓騷。对于问题二只是业务员的携带快件时的速度与不携带时的不同，并且提到了业务员的酬金并且要求费用最省，其他条件没变，我们可以在解决问题一后利用 它得到的结果，对问题二的最优策略进行设计与安排。坛搏乡囂忏蒌鍥铃氈淚。对于问题三，将前面所限定的每个业务员每天最多工作 6小时改成了 8小时。 这一条件的改变，对送货路径并没有太多影响，只是业务员工作的分配会发生改变，事实上问

13、题三是问题一和二的衍生。蜡變黲癟報伥铉锚鈰赘。根据实际要求，建立出单目标0-1规划模型，分别针对三个问题列出目标函 数和约束条件，然后利用软件进行求解，得出最终结论，并进行相关的模型评价 与推广。買鯛鴯譖昙膚遙闫撷凄。五、模型的建立与求解5.1问题15.1.1模型的建立本模型考虑用多目标动态规划求解。由于问题一中只要求给出一个合理的方 案，且未涉及到业务员工资问题，故只要满足条件一一业务员的工作时间上限是 6个小时以及每条路线的最大载重量不大于25kg即可，本模型中追加两个目标路程最短 和人员最少。可以通过以下两种方法实现：（1）每一个行程的第一个送货点是距离总部最近的未服务的送货点。用这种方

14、法，即可得到一组运行路线，总的运行公里数，以及总费用。（2）每一个行程的第一个送货点是距离 总部最远的未服务的送货点。然后以该点为基准，选择距它最近的点，加上约束 条件，也可得到一组数据。然后比较两组结果，通过函数拟合即可得到最优化结 果。綾镝鯛駕櫬鹕踪韦辚糴。5.1.2模型的求解由题意可知，平均每天收到总重量为184.5千克，每个人的最大负重是 25kg，184.5即25-7.38则可知至少需要8条路线对这些邮件进行运送。可以通过以下两种方法实现： 驅踬髏彦浃绥譎饴憂锦。（1）每一个行程的第一个送货点是距离总部最近的未服务的送货点。用这种方法，即可得到一组运行路线，总的运行公里数，以及总费用

15、。猫虿驢绘燈鮒诛髅貺庑。（2）每一个行程的第一个送货点是距离总部最远的未服务的送货点确定业务员的送货路线，采取多目标动态规划法，根据送货点的位置和快件的质 量，我们进行送货点的划分，划分时遵循以下的准则：锹籁饗迳琐筆襖鸥娅薔。1、两个送货点间距最近；2、尽量沿这实际道路的方向选取送货点；3、使区域经过尽量多的点4、经过的送货点快件的总质量不超过 25kg即:830目标函数：mi n 2pj(jxjy)i W i W308 Wjj = 1i =1Wj - Pj - 030约束条件为: wija 25j2Pj(jxjy)30256 j=iPij 二 0或Pij = 1 Wjj 二 0或wij方案一

16、：每一个行程的第一个送货点是距离总部最近的未服务的送货点开始k)找离原该点最近的点 v，且 该点的访问标志设为被访 问，该点快递重量为w， 出该点。 ra找点v最近的点，快递重量 为w1，且w1+w25，当其不 成立时找次远点。到合件7占八、不 符 条 的 时構氽頑黉碩饨荠龈话骛|找到符合条件的点，且不 止一个时选择快递重量最 重的那个点，访问标志设 为被访问，并输出该点， 赋值给 V，且w=w+w1 ；J 取原点为0点，离最近的送货点是1点，离1点最近的时3点，离3点最 近的4点，离4点最近的是5点，这时我们发现离5点最近的是2点，但根据 条件2点的快件总量为8.2kg，加上1、2、3、4、

17、5点的重量已经超过了 25kg。 而这时的1，3, 4，5的重量之和为24kg，所以将1，3，4，5点划分为一个 区域，同理我们可以按照上面的方法划分区域，可以得到如下的送货路线 輒峄陽 檉簖疖網儂號泶。线路编号送货路线路程（公 里）负重站点数时间（小 时）线路10-1-3-4-5-0322441.946线路20-2-6-7-13-04424.242.4267线路30-9-8-12-10-04222.942.3467线路40-16-17-20-14-15-23-09023.564.6线路50-11-22-21-19-07424.933.46线路60-27-26-0762223.7067线路70

18、-18-24-25-06824.733.75线路80-29-28-30-09818.334.42总计524184.53026.6561现在对路线进行优化：由于论文格式问题，举例选取第一条路线，现在0-1-3-4-5这四个送货点之间的最优访问路径安排就是一个典型的单回路 问题。可以通过单回路运输模型-TSP模型求解。通过lingo程序（附录2）解决 路线的选择。得到第一条路线优化后的路线为0-1-3-4-5-0 。尧侧閏繭絳闕绚勵蜆贅。用以上方法可以得到其它的路线（1）0-1 -3-4-5* 0（2）0 二，13_- 7 _6 0一k（3）0_1012 - 89 卜 0_（4） 0 _眇 17

19、- 20 _1415 - 23 0* * 识饒鎂錕缢灩筧嚌俨淒。ooo O19 - 2 1_220 r |7 |7 |76 7 826_0 _24 . 250 #30 r280 .则站点数，所用时间，总载重（kg）,总路程（km）如下：线路编号送货路线路程（公里）负重（千克）站点数时间（小时）线路10-1-3-4-5-0322441.9467线路20-2-6-7-13-04324.242.3866线路30-9-8-12-10-04222.942.3467线路40-16-17-20-14-15-23-09023.564.6线路50-11-22-21-19-07224.933.38线路60-27-

20、26-0762223.7067线路70-18-24-25-06824.733.75线路80-29-28-30-09618.334.34总计522184.53027.4299优化前后的路程和时间的比较如下：27路程比较优化前I优化后由表共有八条路线，其中线路1和线路6累计时间不足6小时，可选派一名快递员分两次运送。 同理，线 路2和3也可以由一名快递员运送。所以整个过程只需要 6名快递员。凍鈹鋨劳臘 错痫婦胫籴。快递员1：线路1,线路6；快递员2:线路2,线路3； 快递员3:线路4 ;快递员4:线路5；快递员5:线路7； 快递员6:线路8；方案二：每一个行程的第一个送货点是距离总部最远的未服务的

21、送货点。分析方法和方案一相似，只不过是从离原点的最远端开始优化前线路编号送货路线路程（公里）负重站点数时间（小时）线路10-30-29-28-23-15-09624.154.673线路20-26-27-8-07524.333.500线路30-24-25-19-0682533.220线路40-18-17-20-16-06421.443.227线路50-21-22-11-10-9-0522554.673线路60-14-13-12-05222.332.580线路70-7-4-3-03418.731.860线路80-5-6-2-1-03423.742.027总计475184.53025.76同方案一，

22、进行优化优化后的路线:线路编号送货路线路程（公里）负重站点数时间（小时）线路10-29-28-30-23-15-09124.154.473线路20-8-26-27-07624.333.540线路30-19-24-25-0682533.22线路40-16-17-18-20-05821.442.987线路50-9-11-21-22-10-0542552.993线路60-12-13-14-05222.332.58线路70-3-7-4-03218.731.78线路80-1-6-5-2-03023.741.867总计461184.53023.44优化前后比较:路程比较线路1线路2线路3线路4线路5线路6

23、线路7线路8优化前优化后时间比较线路1线路2线路3线路4线路5线路6线路7线路咅优化前优化后同样共有八条路线，根据所经历的时间进行划分，确定运送人数。在工作时间小 于6小时的前提下，最终只需要五名快递员，第三条线路和第八条线路由一人完 成第四条线路和第七条线路由一人完成，第五条线路和第六条线路由一人完成。 恥諤銪灭萦欢煬鞏鹜錦。快递员1:线路1；快递员2:线路2；快递员3:线路3,线路8快递员4:线路4,线路7快递员5:线路5,线路6；通过以上两种方法的比较，考虑时间和路程因素我们可以得出:万案路程（km）时间（h）万案一52227.4299万案二46123.44方法二更优其最优路程为461k

24、m所需的总的时间为23.44h5.2问题25.2.1模型建立在业务员送货次数为N的情况下，本问题可以转化为利用0-1整数规划对总 的费用实施满足条件的最小化；再次，对所建立的单目标模型利用Lingo软件求 解，并分析数据，列出每条路线上的时间耗费表；最后，根据上述表中的数据， 利用最佳匹配的原理，对业务员的人数安排进行重新调配， 得到总行运路程最小 情况下，快递公司所需业务员人数最少的策略，此时即为一种合理的方案。鯊腎鑰诎褳鉀沩懼統庫。类似于问题一的研究方法，可以将本问题的方法分析如下：问题中由于业务员所得的费用是最主要的，业务员安排、路线选择都是为了 总费用的最小化提供条件，所以应首先考虑路

25、费，之后再考虑业务员的安排。为 了使总能够费用最少，总的思路是先送货给离快递公司最近切块间最重的送货 点，以此类推，在保证时间、载重量有限的前提下，沿途把快递送完，最终让业 务员最远点空载返回。根据这一思路，全部路线业务员的重载费用可表示为：硕癘鄴颃诌攆檸攜驤蔹。3aj(jx jy)从上式可以看出，业务员的重载费用是恒定的，又由于总费用为重载与空载费用 之和，所以总费用的确定就可以转化为满足一定条件下的各路线的最远点的选择 问题。某路线业务员经过的路径选择应遵循以下原则：阌擻輳嬪諫迁择植秘騖。（1）近者优先原则。某业务员最近起始送货点的选择直接关系到费用的多少，所以该业务员在沿途往送货终点站中

26、应尽量把较近点的快件送完，不让下一条路线再把较近点作为起始送货站。氬嚕躑竄贸恳彈濾颔澩。（2）不走冤枉路原则（即只能向上或者向右走）。一方面，离原点（快递公司）较远的送货点坐标应分别大于离原点较近送货点的 坐标，在各个坐标上均不走回头路，即按图（a）中的路线前进，而不按 路线前进：釷鹆資贏車贖孙滅獅赘。3O起始点另一方面，由于在路途相等的条件下，重载费用要比空载费用大得多，因此，尽 量让业务员空载行走（3）坐标贴近原则。在同一条路线中，离原点较近送货点的坐标仅次于较远点 的坐标。四是，路线较少原则。路线多，一方面，相对最远点的选择多，跑的空 路多，费用就多；另一方面，过分地强调短暂效益，出动路

27、线多，会引起业务员 的反感，不利于以后的人员控制。 怂阐譜鯪迳導嘯畫長凉。根据上述分析及基本假设，业务员送货的费用可以表示如下：业务员携带快件时公司应付费用为:由于业务员不携带快件时的速度是 30千米/小时，酬金2元/千米，因此，业务员不携带快件时，公司应付费用为:N 30昇讣jy)谚辞調担鈧谄动禪泻類。根据题意，业务员携带与不携带快件时，按第i条路线派送快件所需时间分 别为tpii（jx jy）120tpij（jx jy）t230因此，本问题的时间约束可以列为t_Pii(jx jy)20Pij(j30 jy)630wii306 鬥 ij根据上述分析及基本假设，本问题的模型可表示为30N 30

28、目标函数：min 、 3aj(jx jy) 2pij(j jy) j = 1 ji = 1j = 1 j约束条件:Pi ijPj(jx jy)pj(jx +3020应丄306j=w - 61 ijP厂 0或 Pj二 1 w.二 0或w二，ijij30、p pi ijN、w. 円ijw p. ij ij30、w.a j根据模型，通过C+编程（程序见附录）可得结果如下表:线路编号送货线路时间（小 时）路程（公 里）费用负重（千 克）10-1-3-8-13-0(2.4166742792.922.120-2-4-7-14-02.544969.524.730-6-5-20-18-3004.6666792

29、1852.423.840-9-12-19-0：2.75541498.221.950-10-11-21-23-03.66667721352.419.260-16-17-24-28-0I 4.33333882261.822.970-22-29-0：3.75821506.714.980-15-27-03.16667681577.615.490-25-26-03.41667742019.219.661613830.7线路1和线路9累计时间不足6小时，可选派一名快递员分两次运送。 同理，线 路4和8也可以由一名快递员运送。所以整个过程只需要 7名快递员。嘰觐詿缧铴嗫偽純铪锩。快递员1：线路1,线路9,快

30、递员2:线路2；快递员3:线路3 ;快递员4:线路5;快递员5:线路6;快递员6:线路7;快递员7,线路4, 85.3问题3模型及其求解由于问题三为问题一和问题二的衍生，所以该模型在问题二的基础上重新考虑时 间这个约束条件。因此由问题二的模型即可求得问题三的结果。 熒绐譏钲鏌觶鷹緇機库 该模型条件为：30N 30min 33)眼 jy) 一 2%眼 jy) pi j y hi pi ij y30、p. PI ijw p. ij ijs.t30、w.a.Pi ij jPjj(jx20Pjj = o或 pijjy) pij (jx jy)i 30 门U1 w - 86j=i ij二 i W二 0或

31、W二 i，ijij30通过C+语言编程（程序见附录）可得结果如下表:路线时间路程费用线路i0-i-3-8-i3-02.4i642：792.9线路20-2-4-7-i4-02.544969.5线路30-6-5-20-18-30-04.66667921852.4线路40-9-12-19-02.75：541498.2线路50-10-11-21-23-03.66667721352.4线路60-16-17-24-28-04.33333：882261.8线路70-22-29-03.75821506.7线路8:0-15-27-03.1666768P 1577.6 线路90-25-26-03.41667742

32、019.2由表共有九条路线，其中线路3和线路8累计时间不足8小时，可选派一名快递员分两次运送。 同理，线 路6和9也可以由一名快递员运送，线路 5和线路7选一名快递员，线路1和 线路4、线路2派一名快递员。所以整个过程只需要 4名快递员。鶼渍螻偉阅劍鲰腎邏 蘞。每个快递员负责的路线分别为：快递员1：线路3,线路8，快递员2:线路&线路9；快递员3:线路5、线路7 ； 快递员4:线路1、线路2、线路4。六、模型的评价与推广6.1模型的优点（1）模型系统的给出了业务员的调配方案，便于指导工作实践。（2）模型简单明了，容易理解与灵活应用。（3）模型的方法和思想对其他类型也适合，比如灾情考察、邮局递送

33、、车辆 运输等，易于推广到其他领域。（4）本模型方便、直观，易于在计算机上实现和推广。 比如灾情考察、邮局递送、6.2模型的缺点（1）模型给出的约束条件可能也有不太现实的。（2）对街道的方向，客户的快件量的假设有待进一步改进。6.3模型的推广（1）本模型不但适合于快递公司送货问题， 还是用于一般的送货以及运输题,只需要稍微改动模型即可。（2）模型方便、直观，可以实现计算机模拟。（3）建模的方法和思想可以推广到其他类型，如车辆调度问题等。七、参考文献1 姜启源，谢金星.数学模 型M.北京：高等教育出版社2003.2 唐焕文，贺明峰编，数学模型引论-3版，北京，高等教育出版社,2005.3 .3

34、快递公司送货策略，http:/we ，纣忧蔣氳頑莶驅藥悯骛。2013.8.16.八、附录附录1：各送货点之间的距离（含原点）0569118141615121420202122281824282721272136342937344441465054699111071:1515lb172315192322IE222031292432293936416505548109121：E18141516221218222115212530282331283835409450499767131311121319151519181218202?2520282535323711654055561117171110

35、111711131716102C24252318262333303589495068111622221613142010162019132529282621292636333814989560&11162222161181861014137252926201523203027321611107586051016161056121210121151923201813211828253015109661111505111156713171513121014182119142219292631127127111616105068g91016222016151515132422172522322934

36、141318131722221611606611161428262013211372220152320302732201518131722221611S60611168282620112177161813171424212620151411111616105S6605108222014715g13ie149171424212621161512101311569111150571715961014IS151381613232025221716131114367101616105012121065519232012715122219242123221917201312131614887120242

37、216717711814996161318181512151110612172228282217122406101773135321615192226232824191815131610101520262620151022606155293330101315202021222823221917201412131620201496161060972327246791416151827222118161913111215131176571715901014181572107171419281615121013751015212115105177571002428251381615232025272

38、221132025251914151379141973129231424069211614917141921202520242929231813771318231135332718286Q152520181323202536313027252826202124221616152083230241525g1502217151014g103429282523262018192220181413121416W6713212522057121013142924232018211513141715139879151372816201750871512173732312826292321222523171

39、716159191591016141815780576934292825232620181922201414131262220147159131012750107124439383533363028293230242423221626201617231723141015710056413635323033272526292721212019132321151420142091312675054641403735383230313432262625241：E2E221819251925101417g12650附录2:问题1路线优化:model:sets :city / 1. 5/: u;link

40、( city, city):dist,!距离矩阵；x;en dsetsn = size( city);data :!距离矩阵，它并不需要是对称的dist=0 70 115 90 9570 0 46 21 50115 46 0 30 3290 21 30 0 4895 50 32 48 0;en ddata!目标函数；min = sumi nk: dist * x);FQFCity( K):!进入城市K;sumcity( l)| I #ne# K: x( I, K) = 1;!离开城市K;sumcity( J)| J #ne# K: x( K, J) = 1;);!保证不出现子圈；for(cit

41、y(l)|l #gt# 1:for( city( J)| J#gt#1 #an d# I #ne# J: u(I)-u(J)+n*x(l,J)=n-1););!限制u的范围以加速模型的求解，保证所加限制并不排除掉TSP可题的最优解；for(city(I) | I #gt# 1: u(I)=n-2 );!定义X为01变量；for( link:bin( x);End附录3：问题2, 3路线求解：#in clude #in clude #in clude #defi ne M 1000 using n amespace std;struct no deint x;int y;int num;floa

42、t weight;node v31;int mi ndis31;bool vd31;void create(ifstream &in ,i nt n)int i;for(i=0;i vi. num vi.xvi.yvi.weight;coutvi. numvv(vvi.xvv,vvvi.yvv) vvi.weightvt;颖刍莖峽饽亿顿裊赔泷。int d(node a,node b)return (abs(a.x-b.x)+abs(a.y-b.y);void dis()int i,j;for(i=0;i31;i+)coutvi. nu m 到各点的距离：n;for(j=0;j31;j+)coutd(vi,vj);coute ndle ndl;int n ext1()int k,min=M,tag=0;float w;for(i nt i=1;i31;i+)if(vdi=false&d(v0,vi)w) k=i;w=vi.weight;tag=1;if(tag) return k;else return 0;int next2(i nt k,float w)int min=M,tag=0,m,i;for(i=1;i31;i+)if(vdi=false&d(vk,vi)mi n&w+vi.weightvk .x&vi.y