物流配送系统车辆调度的优化模型

第２７卷第２期　２００８年４月　天　津　工　业　大　学　学　报　ＪＯＵＲＮＡＬ　ＯＦ　ＴＩＡＮＪＩＮ　ＰＯＬＹＴＥＣＨＮＩＣ　ＵＮＩＶＥＲＳＩＴＹ　Ｖｏ１．２７　Ｎｏ．２　Ａｐｒｉｌ　２００８　

物流配送系统车辆调度的优化模型　

张庆一　，赫　威　

（１．天津师范大学管理学院，天津３００３８７；２．天津新华职工大学计算机系，天津３０００４０）　

摘　要：对物流配送系统多车动态集货送货问题进行了研究．分别推导出任意策略下，顾客稀疏和顾客密集时顾客　期望逗留时间的下界，证明了ｍＳＱＭ（ｍ　ＳｔｏｃｈａｓｔｉｃＱｕｅｕｅＭｅｄｉａｎ）策略为顾客稀疏情况下的最优策略．　关键词：车辆调度；优化策略；排队论　中图分类号：Ｆ２２４．３４；ＴＰ３０１．６　文献标识码：Ａ　文章编号：１６７１—０２４Ｘ（２００８）０２—００７７—０４　

Ｏｐｔｉｍｉｚａｔｉｏｎ　ｍｏｄｅｌ　ｆｏｒ　ｖｅｈｉｃｌｅ　ｒｏｕｔｉｎｇ　ｏｆ　ｌｏｇｉｓｔｉｃｓ　ｄｅｌｉｖｅｒｙ　ｓｙｓｔｅｍ　

ＺＨＡＮＧ　Ｑｉｎｇ—ｙｉ　．ＨＥ　Ｗｅｉ　（１．Ｃｏｌｌｅｇｅ　ｏｆ　Ｍａｎａｇｅｍｅｎｔ，Ｔｉａｎｊｉｎ　Ｎｏｒｍａｌ　Ｕｎｉｖｅｒｓｉｔｙ，Ｔｉａｎｊｉｎ　３００３８７，Ｃｈｉｎａ；２．Ｄｅｐａｒｔｍｅｎｔ　ｏｆ　Ｃｏｍｐｕｔｅｒ，Ｔｉａｎｊｉｎ　Ｘｉｎｈｕａ　Ｓｔａｆ　ａｎｄ　Ｗｏｒｋｅｒｓ，Ｔｉａｎｊｉｎ　３０００４０，Ｃｈｉｎａ）　

Ａｂｓｔｒａｃｔ：Ｔｈｅ　ｄｙｎａｍｉｃ　ｍｕｌｔｉｐｌｅ　ｖｅｈｉｃｌｅｓ　ｐｉｃｋ—ｕｐ　ａｎｄ　ｄｅｌｉｖｅｐｙ　ｐｒｏｂｌｅｍ　ｉｓ　ａｎａｌｙｚｅｄ．Ｌｏｗｅｒ　ｂｏｕｎｄｓ　ｏｆ　ｃｕｓｔｏｍｅｒ　ｓ　ｗａｉｔｉｎｇ　ｔｉｍｅ　ａｒｅ　ｏｂｔａｉｎｅｄ　ｕｎｄｅｒ　ｌｅｉｓｕｒｅ　ｔｒａｆｆｉｃ　ｃｏｎｄｉｔｉｏｎ　ａｎｄ　ｂｕｓｙｎｅｓｓ　ｔｒａｆｆｉｃ　ｃｏｎｄｉｔｉｏｎ．Ａｎｄ　ｉｔ　ｉｓ　ｐｒｏｖｅｄ　ｔｈａｔ　ｕｎｄｅｒ　ｌｅｉｓｕｒｅ　ｔｒａｆｆｉｃ　ｃｏｎｄｉｔｉｏｎ　ｔｈｅ　ｌｏｗｅｒ　ｂｏｕｎｄ　ｉｓ　ｏｂｔａｉｎｅｄ　ｕｓｉｎｇ　ｍＳＱＭ（ｍ　Ｓｔｏｃｈａｓｔｉｃ　Ｑｕｅｕｅ　Ｍｅｄｉａｎ）ｐｏｌｉｃｙ．　Ｋｅｙ　ｗｏｒｄｓ：ｖｅｈｉｃｌｅ　ｒｏｕｔｉｎｇ；ｏｐｔｉｍｉｚａｔｉｏｎ　ｐｏｌｉｃｙ；ｑｕｅｕｅ　ｔｈｅｏｒｙ　

物流配送车辆调度问题最早由Ｄａｎｔｚｉｎｇ和　Ｒａｍｓｅｒ于１９５９年首次提出Ｌ１］，得到运筹学、组合数学、　计算科学等学科的广泛关注和研究，并且在运输、航　

空、通讯、电力、工业管理、计算机等领域得到了广泛　应用．实际的车辆动态集货送货问题往往是多车动态　集货送货问题（ｍＤＰＤＰ，ｍｕｌｔｉｐｌｅ　ｖｅｈｉｃｌｅ　ｄｙｎａｍｉｃ　ｐｉｃｋ—　

ｕｐ　ａｎｄ　ｄｅｌｉｖｅｒｙ　ｐｒｏｂｌｅｍ）［２－４］，但是就目前掌握的资料来　

看，对于该问题还没有相关的研究成果．为了更贴切　

地反映实际情况，本文将研究多车动态集货送货问　题，对不同情况下的最优策略进行分析．　

１问题的描述　

随着ＧＰＳ／ＧＳＭ、ＷＡＰ、Ｉｎｔｅｒｎｅｔ等无线接入技术的　

运用及ＸＭＬ语言的开发，使得物流配送企业能够随　

时随地掌握顾客信息、车辆位置信息，快速响应顾客　的需求，为顾客提供动态实时的集货送货服务．顾客　

从产生货运需求到车辆将货物运送到目的地的时间　即顾客在系统中的逗留时间，是动态集货送货服务中　的一个重要考虑因素．顾客在整个系统中逗留时间的　长短是衡量企业服务质量的一个重要指标．　

因此，提出问题：面积为　的正方形区域Ａ中，　

有ｍ辆同类型的单容量车辆（即不允许同车），车辆　

以固定速度　行驶．顾客随机产生于该区域中，且顾　客的出现服从参数为　的Ｐｏｉｓｓｏｎ过程．顾客的位置　

相互独立，且服从区域Ａ中的均匀分布；不同顾客的　

目的地相互独立，服从区域Ａ中的均匀分布，且独立　于客户所在地．车辆需要将顾客（或客户的货物）从其　

所在地运送到其目的地，每次只能运送一名顾客，且　服务类型属于不可间断服务．区域Ａ中不同点之间的　

距离按照其Ｅｕｃｌｉｄｅａｎ空间距离来进行计算．问题的　

目标是获得使顾客期望逗留时间最短的策略．　根据顾客出现的先后顺序来标识顾客，令ｉ为系　

统中第ｉ个顾客；　为顾客ｉ的所在地，Ｄ　为顾客ｉ的　

目的地；ｄ　表示对顾客ｉ进行服务的车辆从其服务ｉ顾　客的前一顾客目的地行驶到　的距离：ｉ顾客从出现　

收稿日期：２００７—１１—２８　基金项露：国家自然科学基金资助项目（７０４０２００９）；天津师范大学教育基金资助项目（５２ＬＪ６５）　作者简介：张庆一（１９５９一），女，讲师．Ｅ－ａｍｉｌ：ｑｉｎｇｙｉ—ｚｈ＠１６３．ｃｏｎ￣ｌ

　维普资讯 http://www.cqvip.com ７８一　天津工业大学学报　第２７卷　

到车辆对其进行服务的时问，即　顾客的等待时问记　

为　；负责对　顾客服务的车辆从ｉ顾客出现到服务　

顾客之前用于服务其他顾客的时问记为　，用于在　

路上空驶的时间记为　；　顾客从出现到被服务完毕　的时间，即　顾客的逗留时问记为　；车辆对　顾客　

的服务时问为ｓ　．综上所述，易知：　＝　，　＝　＋　Ｗｉｄ．假定在稳定状态下，这些随机变量的数学期望都　

存在，分别表示为：　

ｄ＝ｌｉｍ　Ｅ［蝴，Ｗ＝ｌｉｍ　Ｅ［Ｗ　］，Ｗ　＝ｌｉｒａ　Ｅ［Ｗｉ￣］，　｝∞　—＋∞　—＋∞　＝１ｉｍＥ［ＷＪ］，Ｔ＝ｌｉｍ研　，ｓ＝ｌｉｍＥ［ｓＪ．　｝∞　—＋∞　—＋∞　令ｐ＝ｋｓ／ｍ表示服务强度；　表示运用策略　获　

得的客户期望逗留时间；　为最优策略下客户的期望　

逗留时问．　

２车辆调度优化模型研究　

服务强度Ｐ对顾客期望逗留时间有很大的影响．　

对于任一特定策略，当Ｐ增大时，顾客的期望逗留时　问会随之增大，因此本文分别针对ｐ一０和ｐ—ｌ这两　

种具有代表性的情况进行了研究．　

２．１顾客稀疏时的期望逗留时间下界　本节研究当顾客稀疏，即ｐ一０时，对于任意策　略，顾客期望逗留时问的下界．　定理１　当　时，顾客的期望逗留时问下界为：　

ｒ．ｉ￣［ｍｊｎ　ｌｌ　Ｘ－ｘｏ　ｌ１］＋　（１）　

式中，　为顾客所在位置；Ｄ　表示车辆按照位置分布　

策略集合Ｈ中使ＥＩ　ｒａ　ｉｎ　Ｉｌ　。ｌ１］取最小值的策略仃　

进行排列时，车辆分布位置的集合；粕为Ｄ　集合中距　

离　点处顾客最近的车辆所在位置；Ｃ　为常数，Ｃ１　０　５２．　

证明：将顾客　的期望逗留时间　分作３部分：　

Ｔｉ＝ＷＹ＋ＷＳ＋ｓ　（２）　求解　一∞情况下（２）式两端的数学期望，得到：　

Ｔ＝Ｗ％Ｗ％ｓ　（３）　

由于　和Ｄｉ相互独立，且服从区域Ａ中均匀分　布，根据文献［４］可知，面积为　的正方形区域中，两　

相互独立且均服从区域中均匀分布的点之问距离的　

数学期望为Ｃ１　一，即　和Ｄ　之间距离的数学期望　

值．因此有：　

ｓ＝ｌｉｒａＥ［　ｌ：＝　（４）　

则Ｔ＝Ｗ％Ｗｓ＋　（５）　假定车辆按照给定的某种分布策略仃分布于区　

域　中，车辆分布位置集合为Ｄ，则可推导出：　

≥１　ｍｉｎ　Ｅｌｒａｉｎ　ｌｌ　Ｘ—Ｘ０　ｌ１］≥　Ｕ　ＩＤＩ＝ｍ　‰　Ｊ　

，Ｉ，Ｅ　ｒ删ｍｉｎ　ｌｌ　Ｘ－ｘｏ　（６）　

另外，　≥０　（７）　则依式（５）～（７）可导出结论（１）．定理１得证．　

２．２顾客密集时的期望逗留时间下界　本节研究当顾客密集，即ｐ一１时，对于任意策　

略，顾客期望逗留时问的下界．　

引理１　ｄ≥　—　一　（８）　

ｕ、／Ⅳ＋等　

式中，　＝—　；Ｎ为系统中期望队长．　３、／６７ｒ　证明：考虑某一特定顾客Ｊ．，定义如下变量：　为顾客　出现以后，系统中顾客的目的地集合以及车辆所　

在位置集合；　为顾客　的位置；Ｚ￣ｏ＝ｍｉｎ　ｌｌ　一　ｌｌ；　

为顾客　出现以后，在Ｊ．的等待过程中新出现顾客　

的目的地集合，　１＝　１，Ｘ：，…，ＸＮ｝；Ｎ￣＝Ｉ６　ｌ，　０，１；　＝　

ｌｌ　一　。ｌｌ，ｉ＝１，２，…，Ｎ１；Ｚ＊＝ｍｉｎ｛Ｚ＊ｏ，　，…，　．）．　

根据定义，　（ｉ≥１）为独立同分布的随机变量，　

且Ｐ　≤　｝≤　三二－（　≥１，　为正实数）　（９）　

车辆可能从集合ｑｂ０、　中的任意一点行驶到顾客　

处，为　服务．则有：　ｄ＞ｉＥ［Ｚ＊］　（１０）　

定义随机变量　的示性函数厶：　

ｆ　１　＜Ｚ　Ｉｘ＝ｌＯ，Ｘ＞ｚ（１１）　

式中，　为给定的正实数．则有：　ｆ　Ⅳｌ　１　Ｐ｛　｝＝尸｛　＋Ｚ／￣＝ｏ｝＝　

ｆ　、　ｌ—Ｐ｛　＋ＺＩ￣＞Ｏ｝　

由厶为非负整数，则有：　

ｒ　Ｐ｛　＞ｚ｝≥ｌ—Ｅ　＋∑　ｌ＝　

１－Ｅ［Ｉ￣］－Ｅ】∑易１　（１２）　

由于　（ｉ＝１，２，…，Ⅳ１）为一系列独立同分布的随　

机变量，随机正整数Ⅳ　与随机变量系列　相互独立，　

根据文献［５］有：

　维普资讯 http://www.cqvip.com 第２期　张庆一，等：物流配送系统车辆调度的优化模型　．．－——７９－－－——　

Ｅ｛∑　ｌ＝Ｅ［Ｎ　］　（１３）　

则：Ｐ｛　）≥１－Ｅ［Ｉ￣］一Ｅ［Ｎ　［　］　（１４）　

根据Ｅ［Ｎ　］．Ⅳ，Ｅ［，ｚ］＝Ｐ｛　≤名）以及式（９），得：　

Ｐ｛ｚＴ＞ｚ｝＞Ｉ　１一Ｐ｛ｚＴｏ￣　｝－Ｎ　（１５）　

考虑区域Ａ中的任意Ｅ［Ⅳ０１个点的集合　，Ｘ为区域　Ａ中独立于集合　且服从区域Ａ中均匀分布的随机　

点．对于集合　中的Ｅ［Ｘｏ］个点，作半径为　的圆，则：　

Ｐ｛ｚＴ。≤　ｌ≤￣－ｋＥ［Ｘｏ］　（１６）　

由于Ｅ［Ｎｏ］＝Ｎ＋ｍ，则从式（１５）、（１６）可以推出：　

Ｐ｛ｚＴ＞ｚ｝＞Ｉ１一　（２Ｎ＋ｍ）　（１７）　

又已知Ｐ｛　）≥０，则：　

Ｅ［　】≥Ｊ。ｍａｘ｛０，１一Ａ，ｒｒ（２Ｎ＋ｍ）　｝　＝　

Ｊ。（１－ＣＺ２）　

＇ｒｒ（２４Ｎ＋ｍ）一　一　ｖ２－　

由　：　】￣０．２６６，　３、／２７ｒ　

故　ｄ≥Ｅ［　≥　—　．引理１得证．　＾＼ｌ　

定理２当ｐ一１时，顾客的期望逗留时问下界为：　

Ｔ＊￣／２而ｈＡ一　（１８）　

证明：系统稳定性条件为：　

ｓ＋　≤ｍ、　（１９）　人　

将７１理１的结果代入式（１９）得：　

ｓ＋ｊ　≤　（２０）　、／Ⅳ＋等　入　

将公式７１：　＋ｓ，Ｎ：ｋＷ，ｓ：　代入式（２０），　

则可得结论（１８）．定理２得证．　

２．３　ｍＳＱＭ（ｍ　Ｓｔｏｃｈａｓｔｉｃ　Ｑｕｅｕｅ　Ｍｅｄｉａｎ）策略　

ｍＳＱＭ策略将服务区分为ｍ个子服务区，服务区　ｉ（ｉ＝１，２，…，ｍ）内的任一客户　到该服务区６１车辆所　在点的距离，小于客户　到其他任何一个服务区内车　

辆所在点的距离．第　台车辆负责对第　个服务区内　

的客户进行服务，这样就形成了ｍ个随机队列．用图　…，　ｍ】，构造生长点集合的Ｖｏｒｏｎｏｉ多边形集合同．令４，　

表示第　个Ｖｏｒｏｎｏｉ多边形，且Ａ产　ＪＩ（ｉ＝ｌ，２，…，ｍ）．　车辆　负责对第　个Ｖｏｒｏｎｏｉ多边形区域内的顾客按　

照ＦＣＦＳ（ｆｉｒｓｔ　ｃｏｍｅ　ｆｉｒｓｔ　ｓｅｒｖｉｃｅ）原则进行服务．当车　辆服务完毕一个顾客以后，即返回其负责的Ｖｏｒｏｎｏｉ　

多边形的生长点，等待下一个顾客．　

定理３对于ｍＳＱＭ策略，要求为：　

ｌｉｍ　：１　（２１）　』　

证明：令　＝（　）入，表示第　个Ｖ。ｒ０ｎ。ｊ多边形区域　

内顾客的到达率，　＝　表示第　个Ｖｏｒｏｎｏｉ多边形区域　

点Ｘ，令吗＝Ｅ［１ｌ　ｌ　ＰｉｅＡ　］，　＝Ｅ［１ｌ　ｌｌ　ＩＸｅＡ　］，