锐客网

  1. 首页 > 生活百科 > >

环鄱阳湖城市群数学建模代码 环鄱阳湖城市群旅游线路的最优设计数学建模( 三 )

生活百科经验知识


19.5kg，因此对于2，7两点，直接舍去，选5最合适 。
4
符号说明
A：所有配送点的 ***，A={0，1，2，3，…….，n}，其中0代表配送中心
m:
业务员人数
C：任意一点到原点（总部）的距离
C总：表示一条路线所运行的总公里数
i,j:
表示送货点，如i点，j点
K：表示K条路线
qi:
点i的需求量，q0=0，表示总部的需求量
B总K:
K条路线的总运行费用
X：校核时的适应度
Xij:
业务员路线安排
5
模型的建立及求解
5.1
TSP模型的数学描述为：
其顶点 *** 为A
顶点间的距离为C={Cij
i,j∈N,1≤i,j≤n}
m
n
min
∑
∑
CijXij
i=1j=1
满足
n
∑
Xij=1,ⅰi=1,2,?n
j=1
m
∑
Xij=1,j=1,2,?n
j=1
Xij∈{0,1},
i=1,2?n,j=1,2?n，而根据题意，任意两点之间都有通路，即不存在Xij=0的情况 。
根据上述所列的启发式 *** 生成一个行程安排解 。每一个行程的第一个送货点是距离总部最近的未服务的送货点 。
第一条行程中访问了节点0-1-3-4-5-0，是因为1距离原点最近，因此由1
出发，3是距离1点最近的点，而且两处快件量之和为14kg，小于每个人最大负重量，可以继续指配 。接着，4是距离3最近的点，而且三处快件量之和为
19.5kg，仍小于25kg,还可以继续指配 。在剩下未服务送货点中，5距离4最近（其实距离4最近的点有2，5，6，7四个点，然后考虑该点需求的快件量，将其从大到小依次排列，快件量需求大者优先，但超过25kg上限的点舍去 。这里2，7被舍去，故选择了5）总快件量之和为24kg 。再继续扩充，发现就会超出“25kg”这个上限，因此选择返回，所以0-1-3-4-5就为第一条路线所含有的送货点 。
现在0-1-3-4-5这四个送货点之间的最优访问路径安排就是一个典型的单回路问题 。可以通过单回路运输模型-TSP模型求解 。一般而言，比较简单的启发式算法求解TSP模型求解有最邻近法和最近插入法两种 。由RosenkrantzStearns等人在1977年提出的最近插入法，能够比最近邻点法，取得更满意的解 。由于0-1-3-0
已经先构成了一个子回路，现在要将节点4
插入，但是客户4有三个位置可以插入，现在分析将客户4插入到哪里比较合适:
1.插入到（0，1）间，C总=
7+4+5+1+4+9=30 。
2.插入到（1，3）间，C总=5+6+4+9=24 。
3.插入到（3，0）间，C总=5+4+4+11=24 。
比较上述三种情况的增量，插入到（3，0）间和（1，3）间增量最小，考虑到下一节点插入时路程最小问题，所以应当将4插入到送货点3和总部0之间 。接下来，用同样的 ***，将5插到4和0之间，能使该条路线总路程最小，该路线总路程为32km，历时1.96667h 。结果子回路为T=
{0-1-3-4-5-0}.因为街道平行于坐标轴方向，所以它就是最优化路线 。
第二条行程这中，由于所剩下节点中，2距离0点最近，因此由2出发，就可以找到最近点13，接着是7，然后6.这样，第二条优化路线0-2-13-7-6-0就确定了 。用这种 ***，依次可确定以下剩余六条路线 。
具体参看如下图表三（一，二，三，……为路线编号；总重量为该路线所有
节点快件量之和）：
由启发式 *** 得到的可行的行程安排解一：
表三
直观的具体路线图如下：
图一
然后，根据所经历的时间进行划分，确定运送人数 。在工作时间小于6小时的前提下，可作如下分类：
这样，将确定的五种组合情况分别分配给五个业务员去送即可 。
这个解是第一个中间最好解 。在选择可行解1每条行程中的第一个送货点时，选择了距离总部最近的未服务的点 。接下去通过选择距离仓库最远的未服务的点为每条行程的第一个客户生成了可行解2 。为了方便遗传算法的分析，编号将连续进行 。如果继续增加的新的标签的行程和前面可行解1

推荐阅读


上一篇：喝酒后肌肉酸痛是怎么回事

下一篇：上海好乐迪