（控制理论与控制工程专业论文）物流系统中车辆路径优化问题研究.pdf

摘要 法得到的行车路径可大大缩短。 4 . 根据现代物流的特点， 研究了有时间窗的 取货送货一体化问 题 ( p d p t w ) ， 分析了车辆在每个顾客处的等待时间、 车 师的到 达时 间、 开 始服 务时 间 和时 间 窗 对车 辆 路 径的 影响 ， 提出了 一 种并 行、 同时插入算法， 当每个运输需求插入路径时， 该算法同时考虑送货位置和取 货位置的插入情况，与目 前广泛采用的单独插入算法相比， 不仅能更好地满 足顾客需求， 而且在缩短车辆的行驶距离和减少等待时间方面都有显著的效 果，有明显的经济效益。 关键词:车辆路径问题物流配送启发式算法 ab s tr a c t ab s t r a c t wi t h t h e d e v e l o p me n t o f m a r k e t e c o n o m y , l o g i s t i c s h a v e e v i d e n t i m p a c t o n e c o n o m y a c t i v i ty a n d p l a y a n i m p o r t a n t r o l e i n c o u n t ry e c o n o m y d e v e l o p me n t . v e h i c l e r o u t i n g p r o b l e m i s o n e o f t h e m o s t b a s i c a n d i m p o r t a n t p r o b l e m s in l o g i s t i c s d i s t r i b u t i o n a c t i v i t i e s , a n d a t t r a c t t h e re s e a r c h e r s a tt e n t i o n o f d o m e s t i c a n d o v e r s e a s b e c a u s e o f t h e e x t e n s i v e a p p l i c a t i o n a n d o b v i o u s e c o n o m y b e n e f i t . s o s t u d y i n g a p p l i e d a n d e ff i c i e n t o p t i m a l a l g o r i t h m s f o r v e h i c l e ro u t i n g p r o b l e m h a s i m p o rt a n t a c a d e m i c a n d a c t u a l m e a n i n g f o r t h e d e v e l o p me n t o f l o g i s t i c s d i s t r i b u t i o n , i n t e l l i g e n t t r a f f i c a n d t r a n s p o r t a t i o n s c h e d u l e , a n d w i l l o b t a i n t r e m e n d o u s s o c i e t y a n d e c o n o m y b e n e f i t . a c c o r d i n g t o t h e a c t u a l re q u i r e m e n t , t h i s t h e s i s m a i n l y f o c u s o n t h e s t u d y i n g o f t h e m o s t f a m i l i a r a n d e x i g e n t v e h i c l e r o u t i n g p r o b l e ms o n t h e b a s i s o f t h e g e n e r a l a n d s y s t e mi c res e a r c h , a n d p r o p o s e s t h e c o r r e s p o n d i n g s o l v i n g a l g o r i t h m f o r t h e p r o b l e m s . f i r s t l y t h i s t h e s i s i n t r o d u c e s t h e b a s i c c o n c e p t a n d res e a r c h s t a t u s f o r v e h i c l e ro u t i n g p r o b l e m s y s t e m i c a l l y a n d d e t a i l e d l y . s e c o n d l y , t h e f o l l o w i n g f o u r m a i n c o n t e n t s a r e i n v e s t i g a t e d : 1 . s t u d y t h e m u l t i p l e v e h i c l e s ro u t i n g p r o b l e m w i t h s t o c h a s t i c d e m a n d ( mv r p s d ) a n d p ro p o s e t w o p r a c t i c a l l y f e a s i b l e a l g o r i t h m s f o r t r a v e l i n g d i s t a n c e re s t r i c t e d mv r p s d . i n t h e c o m p u t a t i o n o f e x p e c t e d t r a v e l i n g c o s t , t h e o p t i m a l re s t o c k i n g p o l i c y i s t a k e n i n t o a c c o u n t t o a v o i d d e l i v e r i n g g o o d s r e p e a t e d l y a n d i n c re a s i n g t r a v e l i n g c o s t b e c a u s e o f t h e r e m a i n i n g s t o c k i n t h e v e h i c l e b e i n g i n s u ff i c i e n t t o s a t i s f y d e m a n d u p o n a r r i v a l a t a c u s t o m e r l o c a t i o n i n m o s t a c t u a l a l g o r i t h m s . t h e a l g o r i t h m s r u n i n a c c e p t a b l e t i m e . t h e c o m p u t a t i o n r e s u l t s i n d i c a t e t h a t t h e a p r i o r i a l g o r i t h m a n d t h e re o p t i m i z a t i o n a l g o r i t h m i n t h i s t h e s i s n o t o n l y o v e r c o me t h e a b o v e d e f e c t s , b u t a l s o h a v e b e t t e r v a l i d i ty a n d a d a p t a b i l i ty c o m p a r e d w it h o t h e r s i mi l a r a l g o r i t h m s . 2 . a c c o r d i n g t o a c t u a l re q u i r e me n t , e x t e n d t h e t r a d i t i o n a l s i n g l e - d e p o t v e h i c l e r o u t i n g p r o b l e m w i t h c o n s t r a i n e d b a c k h a u l s , a n d p r o p o s e a n i n t e g r a t e d o p t i m a l a l g o r i t h m a n d s e v e r a l re d u c t i o n c o m p u t a t i o n p o l i c i e s t o d e a l w i t h m u l t i - d e p o t s v e h i c l e r o u t i n g p r o b l e m w i t h c o n s t r a i n e d b a c k h a u l s . t h e o u t c o me o f t h i s a l g o r i t h m c a n s a v e mu c h t r a v e l i n g c o s t a n d i m p r o v e t h e r u n n i n g ab s t r a c t e ff i c i e n c y . c o m p u t a t i o n r e s u l t s s h o w t h a t i n m u l t i - d e p o t s v e h i c l e r o u t i n g p r o b l e m t h e b a c k h a u l s t r a n s p o r t a t i o n c a n s a v e m u c h t r a v e l i n g c o s t a n d t h e a l g o r i t h m i n t h i s t h e s i s i s v e ry e f f i c i e n t . 3 . s t u d y t h e v e h i c l e r o u t i n g p r o b le m w i t h s i m u l ta n e o u s p i c k u p a n d d e l i v e ry a n d p r o p o s e a n e f f i c i e n t a l g o r i t h m f o r t h i s p r o b l e m . a c c o r d i n g t o t h e i m p a c t o f v e h i c l e s r e s i d u a l c a p a c i t y a n d c u s t o m e r s n e t l o a d o n rou t i n g c o n s t r u c t i o n , a n i n t u i t i o n i s t i c m a t h mo d e l i s e s t a b l i s h e d . p r o p o s e a n i n s e rt i o n c r i t e r i o n b a s e d c u s t o me r s n e t l o a d wh i c h c o n s i d e r c u s t o me r s n e t l o a d and v e h i c l e s r e s i d u a l c a p a c i t y w e l l a n d c an p r o d u c e m o re f re e d e g r e e o f i n s e rt i o n f o r s u b s e q u e n t c u s t o m e r s . t h e c o m p u t a t i o n re s u l t s i n d i c a t e t h i s m e t h o d c an s a v e t r a v e l i n g d i s t a n c e g r e a t l y c o m p a r e d w i t h o t h e r i n s e rt i o n c r i t e r i o n s . 4 . a c c o r d i n g t o t h e c h a r a c t e r i s t i c o f m o d e m l o g i s t i c s , s t u d y t h e p i c k u p a n d d e l i v e ry p r o b l e m w i t h t i m e w i n d o w s and a n a l y z e t h e imp a c t o f v e h i c le s w a i t i n g t i me a t e a c h c u s t o m e r , a r r i v a l t i me , s t a rt i n g s e r v i c e t i m e and t i m e w i n d o w s o n v e h i c l e r o u t i n g . a p a r a l l e l s imu l ta n e o u s i n s e r t i o n a l g o r i t h m i s p r o p o s e d w h i c h t a k e s i n t o a c c o u n t t h e i n s e rt io n o f t h e d e l i v e ry p o s i t i o n and t h e p i c k u p p o s i t i o n s i m u l t a n e o u s l y . t h i s m e t h o d c an s a t i s f y c u s t o m e r s r e q u i r e m e n t w e l l , s a v e t r a v e l i n g d i s t a n c e and r e d u c e v e h i c l e s w a i t i n g t i m e o b v i o u s l y c o m p a r e d w i t h t h e s i n g l e i n s e rt i o n a l g o r i t h m a d o p t e d w i d e l y . k e y wo r d s : v e h i c l e rou t i n g p r o b l e m l o g i s t i c s d i s t r ib u t i o n h e u r i s t i c 南开大学学位论文版权使用授权书 本人完全了 解南开大学关于收集、 保存、 使用学位论文的 规定， 同意如下各项内容:按照学校要求提交学位论文的印刷本和电子版 本; 学校有权保存学位论文的印刷本和电 子版，并采用影印、缩印、 扫描、 数字化或其它手段保存论文; 学校有权提供目 录检索以 及提供 本学位论文全文或者部分的阅览服务; 学校有权按有关规定向国家有 关部门 或者机构送交论文的复印件和电子版; 在不以 赢利为目 的的前 提下，学校可以适当复制论文的部分或 全部内 容用于学术活动。 学 位 论 “ 作 者 签 “ :-g 竿 2, 0 0 6 年 / z 月 1 9 日 经指导教师同 意，本学位论文属于 保密， 在年解密后适用 本授权书。 指导教师签名: a -0 学位论文 作者签名: 哎 逮 竿 解密时间: 尹 r 年月日 各密级的最长保密年限及书写格式规定如下: 内 部 5 年 ( 最长5 年，可少于5 年) 秘密1 0 年 ( 最长 1 0年，可少于 1 0 年) 机密2 0 年 ( 最长 2 0年，可少于2 0 年) 南开大学学位论文原创性声明 本人郑重声明:所呈交的学位论文，是本人在导师指导下，进行研究工作 所取得的成果。除文中己 经注明引用的内容外， 本学位论文的研究成果不包含 任何他人创作的、已公开发表或者没有公开发表的作品的内容。 对本论文所涉 及的研究工作做出贡献的其他个人和集体，均己 在文中以明 确方式标明。 本学 位论文原创性声明的法律责任由本人承担。 学 位 论 文 作 者 签 名 : f 逮 j 2 0 9 6 年 / 之月 / 2日 第 ! 章绪论 第 1 章绪论 1 . ， 引 言 随 着社会市场经济的发展，物流对经济活动的影响越来越明显，对国民 经济的发展起着举足轻重的作用，引起了国内外研究者的广泛关注。 物流这个概念最早出现在 1 9 0 1 年，由 美国的约翰. f . 格鲁维尔在 农产 品流通产业委员会报告中第一次论述了影响农产品配送成本的各个因 素， 从而开始了认识物流的过程。美国的物流管理协会给出了物流的定义为:物 流是供应链流程管理的一部分， 它通过有效率和有效力的计划， 实施和控制 商品的储存、流动、 服务以 及相关信息，来满足从原产地到消费地过程中的 消费者的需要。 1 9 5 6年， 日本从美国引入了物流概念， 并且对物流的含义做了新的论释， 日本学者指出在物流活动中，流通的物品不仅仅指商品，还包括商品消耗后 产生的各种废弃物品。 我国是在 2 0 世纪 8 0年代初引入物流的概念，在 2 0 0 1 年 8月 1日正式 实施的 中华 人民 共和国国家标准物流术语中将物流定义为: 物品从供应 地向接受地的实体流动过程中， 根据实际需要， 将运输、储存、装卸、搬运、 包装、加工、配送、信息处理等基本功能实施有机结合。 目前，世界上一些发达国家和地区的物流产业已成为国民经济的支柱产 业. 美国 作为物流概念的发 源地， 已经形成了比 较成熟的 物流管理体制。 2 0 0 0 年美国物流产业的总规模约为 9 5 0 0亿美元，几乎为高技术产业的 2倍，占 美国国内生产总值的 1 0 %以上，并以年均 2 3 %的速度增长。我国引入物流 的 概念较晚， 企业的物流管理从理论到实践都比 较薄弱， 2 0 0 3 年， 我国物流 产业实现增加值7 8 8 0 亿，占国内生产总值的6 . 5 %1 ，因此需要采取有效的 措施提高我国企业的物流管理水平。 配送是物流中一个重要的直接与消费者相连的环节，配送过程可以定义 为: 将货物从物流集结点送达收货人的过程。 配送是在集货、 配货的基 础上， 完全按照用户的要求，包括货物种类、品种搭配、需求数量、运输时间等方 第 1 章绪论 面的要求所进行的运送过程，是 “ 配”和 “ 送”活动的有机结合，其实现过 程 如图1 . 1 所 示 12 1 用户 工厂 图 1 . 1 物流配送流程图 由图中可见，配送过程主要包括 以下几部分: ( 1 )集货过程:从生产厂家进货以及集结的过程。 ( 2 )配货过程:根据各个用户的不同需求，在配送中心将其所需要的货 物挑选出来的过程 。 ( 3 ) 货物的装载:根据货物的 特点以及装载车辆的容量限制，选择合适 的 方式装载货物。 ( 4 ) 配送路线的确定:根据待服务顾客的需要， 选择合适的路线为所有 的顾客运输货物。配送路线选择的合理与否对配送服务具有决定性的作用， 直接影响到配送成本、服务质量以及经济效益等方面。 因此在许多物流配送系统中，管理者们需要采取有效的配送策略以提高 服务水平、降低货运费用。 在配送运输中，由 于配送用户多，城市交通路线 又比较复杂，如何组成最佳行车路线，如何使配装和配送路线有效搭配等， 是配送运输的特点，也是难度较大的工作。于是采用科学的、合理的方法来 确定配送路线， 成为提高物流配送车辆效益、 实现物流配送科学化的重要途 径.因此，设计合理、有效的车辆路径方案，尽量减少车辆数量和配送里程 就成为非常实际的问题， 其中车辆路径安排问题也成为了03待解决的一个重 要问题。车辆路径优化问题在物流配送管理中起关键性的作用，也是当前电 子商务活动中必不可少的内 容。 车 辆 路 径问 题 ( v e h ic le r o u ti n g p r o b le m v r p ) 自1 9 5 9 年由d a n t z ig 3 1 首 次提出以来， 一直是物流配送活动中的最基本的问题之一，由于其应用的广 泛性和经济上的重大价值， 一直受到国内外学者的广泛关注。关于 v r p的 第 i 章绪论 研究和应用最初来 自于公共服务行业，如学生班车路径、银行运钞车路径等 问题。后来，随着电子商务和物流配送业的发展，车辆路径问题在水运、航 空、通讯、电力、工业管理 、计算机应用、邮政快递、高速公路配货等许多 行业中也得到了广泛的应用。 所以， v r p 作为典型的组 合优化问题， 是运筹学领域研究的热点， 其各 类问题模型在现实中有着广泛的应用。研究 v r p高效率的智能启发式算法 对于促进物流配送、 智能 交通、运输调度等领域的发展也具有实际意义， 将 获得巨大的社会和经济效益。 1 . 2 车辆路径问题的描述 李 军等 在 物 流配 送 车 辆优 化调 度 理论 与 方 法 一书 中 z 1， 将车 辆路 径 问题定义为:对一系列装货点和 ( 或) 卸货点， 组织适当的车辆路线访问它 们，并满足一定的约束条件 ( 货物的需求量、发货量、交发货时间、车辆容 量的约束、 车辆的行驶里程限制、顾客服务时间限制等)下，达到一定的目 标 ( 如行驶路程最短、行驶费用最少、行驶时间尽量少、使用车辆数尽量少 等)，如图 1 . 2 所示。 图 .2 v r p 示意图 在车辆路径 问题的实现中，通常要考虑下列一些组成要素: 1 .目标函数 根据待解决问题的实际需要，从车辆调度者和待服务的顾客两个方面来 第 1 章绪论 衡量车辆路径的有效性， 涉及的目 标函数主 要有: ( 1 ) 最小化使用的 车辆数量:当使用车辆涉及到固定成本的消耗时，那 么使用尽量少的车辆数会节约大量的车辆固定成本的消耗， 从而有效的降低 车辆的行驶费用; ( 2 ) 最小化车辆的 总行驶距离:这是使用最广的一种目 标函数， 使所有 车辆的总行驶距离最短; ( 3 ) 最小化车辆的行驶时间:通常车辆的 行驶时间和行驶距离有直接的 关系，因此这两种目 标函数经常交替使用; ( 4 ) 最小化路径的持续时间:指车辆完成服务的 所有时间， 包括车辆的 行驶时间、等待时间、装卸货时间以及中间司机的休息时间等; ( 5 )最小化顾客的不满意度: 这是从顾客的角度出发考虑的一种目 标函 数， 通常 将所有顾客的等待 服务时间的大小以 及顾客所需货物运输时间的长 短作为衡量顾客满意度的准则。 2 .车场 ( 1 )单车场:所有的 车辆都停放在同一车场内; ( 2 )多车场:所有的车辆停放在多个车场内，根据顾客距离车场的远近 决定由哪一个车场为其提供服务: ( 3 )闭合车场: 所有的车辆由 车场出发，服务完顾客后再返回相应的车 场: ( 4 )开放式车场:车辆由车场出发， 服务完顾客后不需要返回车场，可 以停放在其它地方。 3 .车辆的约束 ( 1 )车辆的种类和容量约束 a.所有车辆的容量、装载要求以及行驶成本都是相同的; b.车辆划分为多种类型，每种类型车辆的载重量、装载要求、固定成 本消耗、可变成本消耗以及数量都是不一样的: ( z ) 行驶里程的约束:限制每条路径的最大行驶里程或者司机连续工作 的最大时间; ( 3 )是否需要租赁车辆: 如果车场提供的车辆不能 满足顾客服务的要求， 那么需要考虑租赁车辆来完成货物的运输。 4 .顾客的需求 第 1 章绪论 ( 1 )静态需求: 所有顾客的货物需求都是事先已知的; ( 2 ) 动态需求:事先只能知道哪些顾客需要服务，每个顾客需求的货物 量只能在车辆到达时才能准确知道; ( 3 )时间窗约束:限制顾客的服务时间，要求车辆在指定的时间范围内 到达顾客处服务. 5 .顾客的类型 ( 1 ) 送货顾客:该顾客要求从车场得到货物: ( z ) 取货顾客:该顾客要求将提供的货物运回车场: ( 3 )同时取送货顾客:每一个顾客既要求从车场运输货物，同时也需要 将提供的货物运回车场。 6 路径特征: ( 1 ) 对称路径:任意两个顾客a和 b ，从a到b的距离和从b到 a的 距离是相等的; ( 2 ) 非对称路径:从顾客 a到 b的距离和从顾客 b到 a的距离是不相 等的; ( 3 ) 静态路径:车辆在任意路段上的行驶时间是不变的; ( 4 ) 动态路径:车辆在任意路段上的行驶时间随着天气以 及交通等原因 发生变化。 7 .顾客之间的关系 ( 1 )无约束的服务:顾客之间的服务顺序不受限制: ( 2 )有约束的服务:限制顾客之间的服务 有先后顺序。 8 .货物的装载限制 ( 1 )无限制:不同 顾客的货物可以随意搭配装载; ( 2 )有限制:不同的货物不能随意搭配，需要根据货物的本身特点以 及 特定的运输要求选择合适的装载方式。 ， . 3 车辆路径问题的分类以及研究 在实际运输中，由于顾客需要提供的服务方式不同，车辆路径问题的存 在形式是多种多样的， 根据上述要素的不同 组合， 形成了不同类型的车辆路 径问题，相应的算法设计差别也较大.目前文献中提到的车辆路径问题的类 第 i 章绪论 型主要有下述几种: 3 . 1 装载能力约束的车辆路径问题 装载能力约束的车辆路径问题 ( c a p a c i t a t e d v e h i c l e r o u t i n g p r o b l e m , c v r p ) 是v r p 的 一 种最 基 本的 存在 形 式4 。 在c v r p 中， 所有 的 顾客 类 型 都是相同的， 都需要从车场运输货物或者都需要将提供的货物运回车场， 每 个顾客的货物需求量都是事先己知的，并且不能分割。所有的车辆都停放在 车场，服务完顾客后需要返回车场，所有车辆的容量都是相同的.c v r p 的 目 标就是最小化车辆的总行驶费 用 ( 用行驶距离或者是行驶时间与路径数量 的加权函数来表示)。 c v r p问题可以描述为: 令 g = ( v , a ) 表示一个完备图，其中v = 0 , 1 , . . . , 时为顶点集， a 表 示弧集。顶点1 , ， n 表示待服务的顾客，顶点0 表示车场。有多 辆车停放 在车场， 每位顾客的商品需求量和顾客之间的距离事先己 知， 车辆从车场出 发对顾客进行配送服务，最后返回车场，要求合理安排车辆路径，使总的运 输路程最短或所用的车辆数量最少，并满足以下条件: ( 1 )每条配送路径上各顾客的商品需求量之和不超过汽车的容量; ( 2 )每个顾客只能由 一辆汽车为其运送商品; ( 3 )每个顾客的商品需求量必须一次满足， 不能分开服务。 每条 弧的 长 度c 。 表示 顾 客 之间 的 行 驶距 离( 时 间) 或 顾客 与 车 场之 间的 行驶距离 ( 时间)，如果 g是无向图， 那么表示任意两个顾客之间的距离是 对称 的， 即 c o = c j ;， 那么 我 们 可以 将 该问 题 称为 对 称的c v r p ， 用 s c v r p 表示 ( s y m m e t r i c c v r p ).反之，如果g是一个有向图， 那么该问 题就成 为非对称的c v r p , 简称为a c v r p ( a s y m m e t r i c c v r p ) 。 通常在两种情况 下 都 假设 行 驶费 用 满 足三角 不 等 式 关系 ，即 c lk + c kj - c ,j ， 当 用节 约 算法 求 解 该问题时，要求该三角不等式必须成立。 c v r p 是目 前研究最多的一种车辆路径问题， 国 外学者从上世纪6 0 年代 开始研究c v r p 5 6 7 1 .国内最早对c v r p问 题进行系统研究的是郭耀煌教 授，他从 1 9 8 9 年开始对多种 c v r p问 题进行了研究，并出版了第一部关于 v r p的专著 车辆优化调度8 1 ，此后出现了大量的 c v r p的求解算法 第 1章绪论 1 9 1 1 1 0 ) 1 1 1 2 1 在 c v r p问题中，由于组成要素的特征不一样，产生了多种 c v r p的存 在形式。 首先考虑车场的数量情况，大多数文献研究的是单车场的c v r p , 但是在实际的运输过程中，许多大型的商业企业都建立了多个配送中心，能 够在较大的范围内为更多的顾客提供服务，因此不可避免的引入了多车场 c v r p( 简称为m d c v r p , m u l t i p l e d e p o t s c v r p )的 使用. 在多车场c v r p 中，每个车场拥有一定数量的车辆，负责为其服务范围内的所有顾客提供运 输。每个顾客只能由任意一个车场派出车辆为其服务，并且车辆完成运输任 务后必须返回原车场。要求设计合理的调度方案，使各个车场能够满足所有 用户的货物需求， 并且使车辆的总运输成本最低.在 m d c v r p问题的求解 中， 既要考虑每一个顾客分别由哪个车场服务，同时还要将该顾客指派到合 适的路径 以节约 运输 费用 ，因此 该类问题 比较 复杂 ，研 究的文献较 少 1 ; 1 4 1 1 5 1 6 1 再有服务顾客的车辆类型可以不相同，大多数文献研究的是车辆类型相 同的 c vr p ，这种问题假定所有车辆的容量以及每单位距离的行驶费用都是 相同的，因此求解要相对容易一些。事实上在有的应用场合中，由于顾客需 要的服务要求不同，需要运输的货物不同，一些配送中心配备多种类型的车 辆，每种车辆的容量、 固定费用的消 耗以 及单位距离的消耗都是不同的， 需 要将顾客的货物需求和车辆的容量以及车辆的消耗等综合考虑以最小化车 辆 的 总 行 驶 费 用 17 is ji9 j c v r p 的另一种变形就是带路程长度约束( d i s t a n c e - c o n s t r a i n e d c v r p , 简称为 d v r p )或路径持续时间约束的车辆路径问题，在该问题中每条路径 必须同时满足车辆的容量约束和最大行驶路程长度的限制， 这种问题 的产生 主要是由于考虑到司机的行驶安全，有必要限制其最大的行驶距离或最长的 驾驶 时间 。 在d v r p 中， 每条 弧 段 ( i, j ) e a 对 应 一个 非负 的 长 度c y ( 或t ,; 表示行驶时间) ， 每条路径中包含的弧段的总长度分别不能超过路径的最大 长度 t 。如果各个车 辆的要求不一样，那么其最大的行驶长度可以 分别设为 t k , 11 = 1 , . . . , k .如果弧段的长度表示车辆的 行驶时间， 通常考虑每个顾客都 需要一个服务时间s ; ，表示车辆在该顾客处需要停留的时间， 那么每条路径 的持续时间包括车辆在路段上的行驶时间以及车辆在每个顾客处的服 务时 间 12 0 1 第 . 章绪论 3 . 2 有时间窗约束的v r p 有 时间 窗 的v r p ( v e h i c l e r o u tin g p r o b l e m w ith t im e w in d o w s ， 简 称为 v r p t w) 是 c v r p 的一个扩展。 在v r p t w中， 每条路径不仅有容量约束， 而且每个顾客l 都定义了一个时间窗 e t , , l t , i ， 其中e t , 表示顾客 l 允许的最 早开始服务时间， l 兀 表示顾客i 的最迟服务时间。 如果车辆到达顾客l 的时 间早于e t , ，那么 车辆需要在顾客 i 处等待，直到e t ; 时刻才能开始为顾客1 服务; 如果车辆迟于 l 界时刻到达顾客 i 处， 那么顾客 i 不接受服务或者需要 采取一定的惩罚措施。同时可以为车场。 规定一个时间窗 e t o , l t o l ， 表示车 辆最早可以离开车场的时间为 e t o ，最晚返回车场的时间为 l t o ，相当于限 制了每条路径的最大持续时间。 在v r p t w中，顾客之间的 行驶费 用用行驶时间来表示，即使顾客之间 的行驶距离是对称的， 但是由于为每个顾客规定了 时间窗的约束， 导致了每 条路径具有隐含的方向性，因此通常v r p t w 问 题作为非对称问 题来处理。 v r p t w 问题是一个求解具有最小行驶费用的多条路径的集合，并满足 下述约束条件: ( 1 ) 每条路径从车场出发并最终返回车场; ( 2 ) 每个顾客只能由一辆车服务: ( 3 ) 每条路径中各个顾客的货物需求量总和不能超过车 辆的最大容量; ( 4 ) 每个顾客i 的服务时间在时间窗 e t , , l t , i 内开始。 由 上可知， v r p t w问题是c v r p 问题的一般化， 对于每个顾客i ， 如果 令 e t ; =o , l t , =- i- -,那么 v r p t w 问题就成为 c v r p问题。 v r p t w 是 c v r p的一个非常重要的扩展研究领域，出 现在顾客需要固定调度时间的应 用场合。v r p t w 具有广泛的应用，例如银行运钞车、邮政递送、工业废物 处理、d i a l - a - r i d e 服务、 校车路线安排等应用中。 根据时间窗要求的不同，v r p t w分为两种: 1 .硬时间窗v r p ( v e h i c l e r o u t i n g p r o b l e m w i t h h a r d t i m e wi n d o w s , 简称为 v r p h t w ) v r p h t w是指每个顾客的需求必须在指定的时间窗内完成， 如果超过这 个时间窗，那么得到的解为不可行解，因此硬时间窗 v r p对顾客的服务时 间 要 求 比 较 严 格 12 1112 2 112 3 112 4 1 第 1 章绪论 2 . 软时间窗v r p ( v e h i c l e r o u t i n g p r o b l e m w i t h s o f t t i m e wi n d o w s ， 简 称为 v r p s t w ) v r p s t w是指如果车辆不能在某个顾客要求的时间范围内到达， 那么需 要给予一定的惩罚。 如果车辆在 e 兀之前到达顾客i ， 则车辆需要在该顾客处 等待，增加了时间成本;如果车辆在 l t , 之后到达顾客i 处，则顾客的服务 被延迟，需要支付一定的罚金成本1 25 1 1 2 6 1 1 2 7 1 v r p t w 的相关研究文献较多，近年来国内提出了很多求解 v r p t w 的 启发式算法。 3 . 3 带回程运输的v r p问题 在每一条车辆路径中，如果有的顾客需要从车场运输货物而有的顾客需 要 将提 供的 货 物 运回 车 场， 就 产生 了 带回 程 运 输的v r p 问 题 ( v e h ic le r o u t in g p r o b le m w i th b a c k h a u ls ， 简 称 为v r p b ) 。 v r p b 问 题 要比c v r p 问 题复 杂， 在c v r p问 题中， 车辆只进行一种服务， 即将每个顾客提供的货物运回车场 或者从车场为每个顾客运输货物，而在 v r p b问题中，需要同时考虑这两种 活动。v r p b问题可以描述为: 令g =( v , e ) 表示无向图，v ( v o , v i , v 2 , . . . , v . 表示顶点集合， e = ( ( v ; , vi ) : v ;, v i e v , iy 为 边 集， 在边 集e 上 定义 一 个 距离 矩 阵d = ( d ri) ， 其中d i 满足三角不等式关系.顶点集合被划分成 v ( ( v o ) , l , b ) ，其中v o 是车场， 多辆车 ( 容量相同或容量不同)停放在车场，l表示需要从车场运输货物的 顾客集合，b表示需要将提供的货物运回车场的顾客集合，每一顾客对应一 定数量的送货量或取货量， 要求设计多条行车路线使车辆的总行驶费用最小 并满足下述条件: ( 1 )每条路 径只能由一辆车运送货 物; ( 2 )每条路径从车场出发，最终返回车场; ( 3 )每个顾客只能由一 辆车服务: ( 4 ) 每条路径上从车场运出的货物以及顾客提供的需要运回车场的货 物总量分别不能超过车辆的容量。 在v r p b问 题中， 如果距离矩阵d是非对称的，则该问 题称为带回 程 运输的非对称 v r p ( a s y m m e t r i c v e h i c l e r o u t i n g p r o b l e m w i t h b a c k h a u l s , 第 i 章绪论 a v r p b ) 问 题 2 8 1。 根 据每 条路 径上 送货 顾客 和 取货 顾 客 服务 顺序的 不同 ， v r p b问题分为两种: 1 .有约束的 v r p b问题 有约束的v r p b问题是指车辆装满货物从车场出发， 先将货物运送给需 要的顾客，当车上所有的货物都用完后，再捎带将其它顾客提供的货物运回 车场，以减少空车的行驶里程，节约运输费用，如图 1 . 3所示。当车辆从后 面装卸货时， 这种方式可以 减少重新整理车上货物的工作， 而且一般说来送 货顾客的服务 优先权要高于取货顾客， 应该得到优先服务。 这类问题的研究 文 献 较 多 2 9 1 13 0 13 1 1 lb 图 1 . 3 有约束的 v r p b示意图 2 .混合的 v r p b问题 混合的 v r p b问 题是指车辆可以以任何顺序服务顾客， 在送货的过程中 可以考虑装载其它顾客提供的货物， 不限制顾客的服务顺序， 如图 1 . 4所示。 这种方式适用于车辆两侧开门的结构设计， 中途整理车上货物比 较容易， 必 须保证车 辆行驶过程中 装载的所有货物不能超过车辆的容量， 这种方式比 有 约束 的v r p b 更能 节 约 行驶 费 用 13 2 113 3 1 3 . 4 同时取送货的 v r p问题 在一些实际应用中，每个顾客既需要从车场运输货物，还需要将提供的 货物运回车场， 这种f -i 题称为同时取送货v r p ( v e h i c l e r o u t i n g p r o b l e m w i t h 第 1 章绪论 s i m u l t a n e o u s p i c k u p a n d d e l i v e ry.简称为v r p s p d )。 v r p s p d 1 a7 题可以 描 述 为: 图 1 .4 混合v r p b示意图 有多辆车负责将顾客需要的货物从车场运到顾客处，同时装载顾客提供 的货物运回车场。车场和顾客的位置一定，每个顾客的货物需求量和供应量 一定，每辆车的载重量一定，要求设计合理的行车路线，使总的行驶费用最 小，并满足下述约束条件: ( 1 ) 在车辆的行驶过程中， 每辆车的 装载量 ( 包括送货总量和取货总量) 不能超过车辆的最大容量; ( 2 ) 每个顾客只能被服务一次; ( 3 ) 车辆先为顾客卸货，然后再装载顾客提供的货物。 v r p s p d问题是近年来才兴起的一种 比较复杂的车辆路径问题，相关的 研究文献较少 3 4 3 5 1 1 3 6 1 ，但是具有较强的应用前景和研究价值， 是一个值得 深入研究的问题。 3 . 5 有时间窗的送货和取货问题 前面几种 v r p问题都有一 个共同的特性， 即在每一条路径中所有的货物 从一个地点运出或最终要运回相同的地点。有时间窗的送货和取货问题 ( p i c k u p a n d d e l i v e ry p r o b l e m w i t h t i m e wi n d o w s ， 简称为p d p t w) 是一类 比较特殊的 v r p ，可以描述为: 在一定的地理范围内，分布着不同的顾客，需要在指定的取货位置 o i 第 1 章绪论 装载货物， 并将货物运送到 特定的目 的地d ; 卸载， 而且货物的 装载卸载需要 在指定的时间范围内完成。当在一个区域内存在大量的这种顾客时，需要多 个车辆为这些顾客服务， 在复杂的约束条件下， 合理安排行车路线， 使车辆 的行驶费用最小。在 p d p t w 中，每一项服务都对应一个特定的取货位置和 一个相应的 目的地，要求车辆必须先经过取货位置装载货物，然后将货物运 送到 目的地点卸载。每一条路径中包含多个送货和取货任务，车辆离开车场 和返回车场时车上的装载量为0 . 国外 研究较多的电话叫车服务 ( d ia l- a -r id e ，又可称为 d ia l- a -b u s , d e m a n d - r e s p o n s i v e t r a n s i t 以 及 d e m a n d - a c t u a t e d t r a n s i