起点终点相同的运送计划

《起点终点相同的运送计划》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、起点终点相同的运送计划运输公司、配送中心在运输货物时常常要求车辆在完成运输后要回到出发地。起点终点重合的路径问题也被称为巡回推销员问题。有一个n个节点构成的网络，已知节点间的“距离”，要寻找一条经过所有节点的距离最短的回路。可以用如下数学模型来表示：s.t.其中这是一个整数型线性规划问题，当网络中包含很多节点时，没有有效的算法。一般采用直觉方法和启发式方法，这些方法可在合理的时间内给出一个较优解。例如在直觉上，一定的长度，包含面积最多的曲线是圆形，因此好的路线规划中应该呈凸形或水滴形，并且没有线路交叉。例如下图中b)的路线规划

2、就要比a)好。a)不好的路线规划b)较好的路线规划图6-10路线规划比较启发式方法中很多是贪婪方法，例如最近邻点法，最近插入法等。最近邻点法就是从某点开始，总是找离目前位置最近的、还未到过的节点作为下一点，直到所有节点走完，再回到起点。得到的结果常常是不理想的。最近插入法要更进一步，在选择下一点时，不仅仅只考虑当前的一点，而是考虑所有已走过的点。另外，它每一步是整个回路的扩张，即从一开始它就考虑回到起点的成本。方法描述如下：（1）找出离最近的节点，构成子回路。（2）重复（3）直到T包含所有节点：（3）从子回路T以外的节点中找出

3、离回路T中节点最近的节点，在T中找到边，使最小，将插入之间，即用，代替，构成新的回路T。资料6.13一家面包房每天要向五家零售店送货，各点之间的行车时间如下：（由于交通的问题，同一线路不同方向的行车时间有些不同）表6-6面包房及零售店之间的行车时间自到面包房0零售店1零售店2零售店3零售店4零售店5面包房002450385520零售店122032234518零售店247350152160零售店339271701425零售店457421816042零售店521165721410第1步，找出最小的点5，=41，T={0，5，0}；

4、第2步，离{0，5}最近的点是1，，接下去考虑1插在0，5之间还是5，0之间，因为，，因此插在5，0之间，得到T={0，5，1，0}；第3步，离{0，1，5}最近的点，3，，，，，得T={0，5，3，1，0}；第4步，离{0，1，3，5}最近的点，4，，，，，，得T={0，5，3，4，1，0}；第5步，最后一点是2，，，，，，得T={0，5，3，4，2，1，0}；因此最后的结果是{0，5，3，4，2，1，0}，总运输时间为130。