起点终点相同的运送计划.doc_第1页
起点终点相同的运送计划.doc_第2页
起点终点相同的运送计划.doc_第3页
起点终点相同的运送计划.doc_第4页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

起点终点相同的运送计划运输公司、配送中心在运输货物时常常要求车辆在完成运输后要回到出发地。起点终点重合的路径问题也被称为巡回推销员问题。有一个n个节点构成的网络，已知节点间的“距离”，要寻找一条经过所有节点的距离最短的回路。可以用如下数学模型来表示：s.t. 其中这是一个整数型线性规划问题，当网络中包含很多节点时，没有有效的算法。一般采用直觉方法和启发式方法，这些方法可在合理的时间内给出一个较优解。例如在直觉上，一定的长度，包含面积最多的曲线是圆形，因此好的路线规划中应该呈凸形或水滴形，并且没有线路交叉。例如下图中b)的路线规划就要比a)好。 a)不好的路线规划 b)较好的路线规划 图6-10 路线规划比较启发式方法中很多是贪婪方法，例如最近邻点法，最近插入法等。最近邻点法就是从某点开始，总是找离目前位置最近的、还未到过的节点作为下一点，直到所有节点走完，再回到起点。得到的结果常常是不理想的。最近插入法要更进一步，在选择下一点时，不仅仅只考虑当前的一点，而是考虑所有已走过的点。另外，它每一步是整个回路的扩张，即从一开始它就考虑回到起点的成本。方法描述如下：（1） 找出离最近的节点，构成子回路。（2） 重复（3）直到T包含所有节点：（3）从子回路T以外的节点中找出离回路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；第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，
人人文库> 全部分类> 生活休闲 > 科普知识

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论