《起点终点相同的运送计划》由会员分享,可在线阅读,更多相关《起点终点相同的运送计划(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。