车辆路由问题在邮路规划中的应用研究.pdf

2006 年 1 月中国管理信息化 Jan.,2006
第 9 卷第 1期 China Management Informationization ,
车辆路由问题在邮路规划中的应用研究
程录庆 1 ,胡涛 2
( ,南京 210042;,南京 210000)
摘要本文基于“车辆路由问题”的思想,提出了一种市内邮路规划的路由模型;并结合实例给出了相应的算法,
对实现邮路优化提出了新的思路,并对实现市内邮路规划的计算机决策支持系统有重要的实际意义。
关键词车辆路由问题路由模型算法计算机决策支持系统
中图分类号文献标识码文章编号()
一、引言所要求的时限和频次的基础上,尽可能地节约时间和降低
在实际生产、生活当中,我们经常会遇到这样一类问总的运输费用。
题:(1)商场欲将一批已售出的彩电送货上门,以现有的几下面给出解决这一问题模型的一种可行的算法,此算
辆送货车,如何能将彩电及时、准确地送到客户手中,同时法基于 C/W 算法,是一处启发式算法。
又能节约时间和费用;(2)供电部门应如何安排其抄表人员我们先假定实际 C1
去用户那里抄表才算合理;(3)邮递人员如何从各处的邮箱问题满足以下条件:
a. 从枢纽中心到 C12 C3
中收集邮件;(4)一个医生如何应付多个病人的出诊请求; C2 C4
(5)学校班车如何接送小孩上下课等等。上述所有这些问各个支局以及各支局
题,形式虽然不同,但都可以归纳一个共同点,即都可以抽之间的车辆需要运行
C9 C6
象成多个“车辆”为多个分散的“客户”进行服务,其目标是的最短里程已知: C7
为了节约时间、降低费用。这类问题在国际上称之为“车辆
C10
路由问题”(Vehicle-Routing Problem)。当前我国城市市内车参与邮件运送
邮政运输规划就属于这一类问题。市内邮政运输是连接市 c. 每个支局所需 C5
C8
运送的邮件不超过单
内邮政支局所、邮件处理枢纽中心和干线运邮工具站埠之 C11
间邮件传递的纽带。市内邮政运输具有时限低、频次多、受辆邮车的运载能力
城市道路交通条件和其他客观因素的影响大的特点。传统(如果超过,我们将它图 1
的邮政运输规划主要靠调度人员凭经验行事,管理方式比虚拟成二个(或更多
较粗放,在很多情况下,难以制定出优化的运输路线(即节个)支局以使其需要运送的量不超过车辆的负载能力)。例
约时间和费用的路线)来。应用科学化、系统化的方法进行如:某支局需运送邮件 30 袋,而邮车容量为 20 袋,则可将
邮政运输路线规划是邮政企业提高生产率、降低管理成本其分解为各需运送 15 袋的两个支局,支局位置相同即可。
的必由之路。本文基于“车辆路由问题”的思想,建立了市本算法的基本思路是:先假定从枢纽中心到每个支局
内邮车规划的路由模型,并给出了相应的算法。都有一辆车运送邮件,这样其初始的路径就有 N 条(假定
二、模型及算法支局为{C=ci=1,2 N }。中心点为c0,,即为{c0c1c0,c0c2c0,
,如图,然后以路由里程节余为判据,进行路径
根据邮运生