起点终点相同的运送计划

《起点终点相同的运送计划》由会员分享，可在线阅读，更多相关《起点终点相同的运送计划（4页珍藏版）》请在金锄头文库上搜索。

1、起点终点相同的运送计划起点终点相同的运送计划运输公司、配送中心在运输货物时常常要求车辆在完成运输后要回到出发地。起点终点重合的路径问题也被称为巡回推销员问题。有一个 n 个节点构成的网络，已知节点间的“距离”，要寻,.1nvv.,2 , 1;,.,2 , 1,njnicij找一条经过所有节点的距离最短的回路。可以用如下数学模型来表示： ninjijijxc11mins.t. njijnix1.,2 , 1, 1 niijnjx1.,2 , 1, 1njnixij,.2 , 1,.,2 , 1,1 , 0其中 。的下一站不是节点，表示节点；的下一站是节点，表示节点 jijixij01这是一个整数

2、型线性规划问题，当网络中包含很多节点时，没有有效的算法。一般采用直觉方法和启发式方法，这些方法可在合理的时间内给出一个较优解。例如在直觉上，一定的长度，包含面积最多的曲线是圆形，因此好的路线规划中应该呈凸形或水滴形，并且没有线路交叉。例如下图中 b)的路线规划就要比 a)好。a)不好的路线规划 b)较好的路线规划 图 6-10 路线规划比较启发式方法中很多是贪婪方法，例如最近邻点法，最近插入法等。最近邻点法就是从某点开始，总是找离目前位置最近的、还未到过的节点作为下一点，直到所有节点走完，再回到起点。得到的结果常常是不理想的。最近插入法要更进一步，在选择下一点时，不仅仅只考虑当前的一点，而是考

3、虑所有已走过的点。另外，它每一步是整个回路的扩张，即从一开始它就考虑回到起点的成本。方法描述如下：（1） 找出离最近的节点，构成子回路。1vkv,11vvvTk（2） 重复（3）直到 T 包含所有节点：（3）从子回路 T 以外的节点中找出离回路 T 中节点最近的节点，在 Tkv中找到边，使最小，将插入之间，即用，),(jivvijkjikccckvjivv ,),(kivv代替，构成新的回路 T。),(jkvv),(jivv资资料料 6.13 一家面包房每天要向五家零售店送货，各点之间的行车时间如下：（由于交通的问题，同一线路不同方向的行车时间有些不同）表 6-6 面包房及零售店之间的行车时间

4、自 到面包房零售店零售店零售店零售店零售店012345面包房002450385520零售店122032234518零售店247350152160零售店339271701425零售店457421816042零售店521165721410第 1 步，找出最小的点 5，=41，T=0，5，0；00kkcc5005cc第 2 步，离0，5最近的点是 1，接下去考虑 1 插在 0，5 之间还1651c是 5，0 之间，因为，因此插在 5，0 之间，得22051501ccc17501051ccc到 T=0，5，1，0；第 3 步，离0，1，5最近的点，3，2153c43053503ccc，得 T=0，5，3，1，0；32513153ccc40103013ccc第 4 步，离0，1，3，5最近的点，4，1434c77054504ccc，得 T=0，5，3，4，1，0；36534354ccc29314134ccc80104014ccc第 5 步，最后一点是 2，90052502ccc51532352ccc，得24342432ccc11412142ccc57102012cccT=0，5，3，4，2，1，0；因此最后的结果是0，5，3，4，2，1，0，总运输时间为 130。