物流配送车辆优化调度的综述.pdf

第33卷增刊东南大学学报(自然科学版)Vol133Sup.

2003年9月JOURNALOFSOUTHEASTUNIVERSITY(NaturalScienceEdition)Sept.2003

物流配送车辆优化调度的综述
杨弋顾幸生

(华东理工大学自动化研究所,上海200237)

摘要:物流配送车辆优化调度问题是一类具有广泛应用的强NP难题,本文综合国内外多种参考文
献,阐述了该问题的定义和分类,具体介绍了不同情况下的常见模型和主要算法,并就目前该问题
的研究发展情况做了简要分析和进一步的展望.
关键词:物流;配送;车辆调度;调度
中图分类号:F252文献标识码:A文章编号:1001-0505(2003)增刊20105207

Asurveyoflogisticsdeliveryvehiclescheduling
YangYiGuXingsheng

(ResearchInstituteofAutomation,EastChinaUniversityofScienceandTechnology,Shanghai200237,China)
Abstract:LogisticdeliveryvehicleschedulingproblemisawidelyusedstronghardNPproblem.Inthispa2
per,therecentdevelopmentofthestudyonlogisticdeliveryvehicleschedulingproblemisintroduced,itsdefi2
nitionandclassificationareanalyzed,alsoitsmainmathematicsmodelandalgorithmarediscussedaftercon2
sultinglotsofreference.Finallyitsapplicationsaregivenanddevelopmenttendencyismadefurtherestimate.
Keywords:logistics;delivery;VSP;scheduling

1物流配送车辆调度问题的提出
111物流配送车辆优化调度问题的提出
最初的物流概念(physicaldistribution)是美国学者克拉克在20世纪20年代提出的[1].随着社会经济的发
展,物流已从传统的运输服务发展成为以信息技术和管理为核心的综合物流系统.因此,美国物流管理协会
于1984年正式将物流概念改为了logistics[1].
现代物流配送流程可见图1[2],其中存储环节的要求日益趋向弱化,配送成为最重要的环节,直接为用
户服务.配送的核心部分是配送车辆的集货、货物配装及送货过程,而车辆配送路线的合理优化,对于整个物
流运输速度、成本、效益影响至关重要.根据中国仓储协会对146个企业的调查显示,用于运输的费用占整个
物流费用的比例分别为:在生产企业原料物流中占58%,在生产企业成品物流中占73%,在商业物流中占
52%[3].所以进行配送系统优化,最主要是对配送车辆的优化调度,包括集货线路优化、货物配装及送货线路
优化.

图1配送流程图

物流配送车辆优化调度问题最早是由学者Dantzig和Ramser于1959年首次提出的[4],国外一般称之为
vehicleroutingproblem或vehicleschedulingproblem.一般以为,不考虑时间要求,仅根据空间位置安排线路时称
为车辆线路安排问题VRP;考虑时间要求,安排线路时称为车辆调度问题VSP[5].对VRP与VSP,也有学者不

收稿日期:2003205215.作者简介:杨弋(1972—),男,硕士生;顾幸生(联系人),教授,博士生导师,[e-mail].
106东南大学学报(自然科学版)第33卷

区分两者,只是加上具体约束定语,例如,将有时间要求的车辆调度问题称为vehicleroutingproblemwithtime
windows,等等.由于大多数国外文献习惯采用VRP表述车辆调度问题,本文循例称之为VRP.
物流配送车辆优化调度问题一般可定义为:对于一系列装货点和(或)卸货点,组织合适的行车线路,使
载货车辆有序地通过它们,在满足一定的约束条件(如货物需求量、发送量、交发货时间、车辆容量限制、行驶
里程限制、时间限制等)下,达到一定的目标(如路程最短,费用最少,时间尽量少,使用车辆数量尽量少
等)[3].
112车辆优化调度问题的分类
VRP被提出后,国内外各学科的学者从不同角度,不同方向对它进行了各种研究,并各自按不同的标准
对VRP进行了分类[6,7],综合起来可分为以下几种.
按任务目标区分,有纯装问题或纯卸