基于目标的改进的货郎担问题研究

《基于目标的改进的货郎担问题研究》由会员分享，可在线阅读，更多相关《基于目标的改进的货郎担问题研究（3页珍藏版）》请在装配图网上搜索。

1、基于目标的改进的货郎担问题研究 改进的根底上以江苏省地级市为例，利用MATLAB和LINGO软件模拟出最优路径图，改进算法确定回路，运用搜狗地图获取数据建立并求解数学模型以展开研究.【关键词】TSP问题；动态规划；LINGO；优化算法一、背景介绍货郎担问题也叫旅行商问题，即TSPTravelingSalesmanProblem问题，其要求很简单：在各城市的集合中，找出一条经过每个城市各一次，最终回到起点的最短路径.求解该类问题可以使用精确算法，常用的方法方案，包括构造型算法和改进型算法，主要有遗传算法、蚁群算法、模拟退火算法、人工神经网络、LK算法、人工免疫算法、粒子群优化算法和混合智能算法等

2、.二、问题内容目标假设今年认识实习安排如下，从徐州市出发，需要访问江苏省的所有地级以上的城市，然后回到徐州市.本次实习搭乘我校的自备车，请设计路线要求至少经过每个城市1次，并且总的行驶里程最短.目标假设今年认识实习安排如下，从徐州市出发，需要访问江苏省的所有地级以上的城市，然后回到徐州市.本次实习搭乘我校的自备车，请设计路线要求至少经过每个城市1次，考虑公路的收费问题，假设汽车每千米的油耗是固定的，要求总的费用最少注意：普通公路收费低，高速公路收费高.目标假设今年认识实习安排如下，从徐州市出发，需要访问江苏省的所有地级以上的城市，然后回到徐州市.本次实习搭乘我校的自备车，请设计路线要求至少经过

3、每个城市1次，考虑不同公路的车速限制问题，假设高速公路限速100千米/小时，其余公路限速60千米/小时，不考虑油耗和收费，汽车均按照最高限速行驶，要求总的时间最短.三、模型假设1.假设两个城市之间的往返是互逆过程.2.假设所选路线都是可行的，即没有封路情况.3.假设城市之间高速公路收费固定.4.假设各城市的油价统一，均为国内统一油价.5.假设车辆密度不随时间变化，不考虑车辆密度变化带来的速度变化.6.假设在旅途中的车速一定，且不考虑突发事件干扰大巴的行程.四、模型的建立与求解首先用点来代替每个城市的位置，对江苏省各城市徐州、宿迁、连云港、淮安、盐城、扬州、泰州、镇江、南京、常州、无锡、苏州和南

4、通等按顺序编号为1，2，13.一问题一设城市的个数为n，dij是两个城市i与j之间的距离，xij=0或1，假设一个TSP由城市1，2，3，13组成.当ij，设cij城市i到城市j的距离，设cij=M，其中M是一个非常大的数.设定cij=M将确保我们不会再离开城市i后不会马上到达城市i，此外定义xij=1如果TSP的解是从城市i到城市j，0如果TSP的解不是从城市i到城市j.通过求解：minz=ijcijxij，i=ni=1xij1j=1，2，n.1j=nj=1xij1i=1，2，n.2ui-uj+nn-1ij，i=2，3，n；j=2，3，n.3xij=0或1，uij0.4目标函数给出了包括巡回

5、访问路线中弧长的总长度，约束条件1确保我们到达城市至少一次，约束条件2确保我们只离开一个城市一次，3中的约束条件是表达的关键，他们确保：1包含子巡回路线的任何一组xij都是不可行的也就是它们违反了3；2构成子巡回路线的任何一组xij都是可行的存在一组满足3的uj.为了直观显示江苏省各城市之间的位置关系，我们搜集了江苏省13个城市的经纬度坐标，不相邻城市之间取非常大的数100000km.根据江苏省各城市的经纬度坐标及两两城市之间的最短距离，我们运用Matlab软件模拟出了实习路线效果图，其中每一个“Wingdings2AB表示每个城市，折线表示实习路线，徐州市为实习起点，得到最优实习路线为：徐州

6、连云港盐城南通泰州苏州无锡常州镇江扬州南京淮安宿迁徐州，路线距离总和为：1534.2km.二问题二模型建立与求解对于问题二，运用所建的模型，“最短距离换为“最少费用.由调查得出，汽车百千米油耗约为30L，国内标准油价5.19元/L，且汽车每千米油耗固定，计算出汽车油消耗用为1.557元/km.根据实际道路长度，可以算出汽车油消耗用，再加上路程高速费用，从而可以得到江苏省两两城市之间的最少费用.同样，我们把不相邻的城市的行驶费用设为100000元，即足够大，从而实现不可能选取.我们基于上述模型及行驶费用最小原那么，最优行驶路线为：徐州连云港盐城泰州南通苏州无锡常州镇江南京扬州淮安宿迁徐州，行驶费

7、用总和为2523.25元.三问题三模型建立与求解对于问题三，将模型二中的权值“最短距离换为“最短时间.由题目假设，汽车高速公路限速100千米/小时，其余公路限速60千米/小时，不考虑油耗和收费，根据问题一搜集到的两城市之间道路距离，再从中细化出高速距离与其他公路距离，根据车速，从而计算出江苏省各城市之间所需行驶时间，同样，根据江苏省交通厅的实时交通图及Lingo运行特点，我们把不相邻的城市的行驶时间设为100000分钟，即足够大，从而实现不可能选取.我们以任意两城市之间的行驶时间矩阵为权重矩阵，利用w3i，j1313构造无向图UG3，利用Lingo軟件按改进圈算法求解，首先设C=v1v3vnv

8、3，求出符合要求的最短距离的最优圈circle3，保证从终点返回到出发点的行驶时间也最短.从理论行驶时间模型的结果来看，基于总行驶时间最短原那么，Lingo程序求解的认识实习的最优路线为徐州宿迁淮安南京扬州镇江常州无锡苏州南通泰州盐城连云港徐州，行程总时间为1011min.由于实际路况的复杂性，各路况允许汽车行驶速度的不同，同时为了检验可靠性，我们在高德地图上搜集了城市之间的实际最短行驶时间，这个时间更具有说服力.同样我们基于理论行驶时间模型的算法，以任意两城市之间的行驶时间矩阵为权重矩阵，利用Lingo软件按改进圈算法求解，首先设C=v1v4vnv4，按改进圈算法求出此时的最优圈后，求出符合要求的最短距离的最优圈circle4，保证了从终点返回到出发点的行驶时间也最短.从结果可知，基于实际行驶时间的实习最优路线与理论时间模型的最优路线相同，说明理论时间模型结果具有很高的可靠性，具体行驶路线与理论时间模型优化路线一致.【参考文献】【1】管琳，白艳萍.用分支定界算法求解旅行商问题J.中北大学学报自然科学版，202102：104-107.方法J.华东交通大学学报，202105：29-33.【3】WLWinston.运筹学应用范例与解法M.杨振凯，等译.北京：清华大学出版社，2021：572-599.