第6卷第5期2006年10月交通运输系统工程与信息JournalofTransportationSystemsEngineeringandInformationTechnologyVol16No15October2006:100926744(2006)0520065205多配送中心车辆调度问题的模型与算法研究(北京交通大学交通运输学院,北京100044)摘要:在对多配送中心车辆调度问题进行直观描述的基础上,建立了该问题的数学模型。提出了采用距离最近分配法将多配送中心车辆调度问题分解为多个单配送中心车辆调度问题进行求解的策略.,设计了求解多配送中心车辆调度问题的算法,.,用本文设计的算法求解多配送中心车辆调度问题,,计算效率较高,收敛速度较快,关键词::U491ModelandAlgorithmforMulti2DepotVehicleSchedulingProblemLANGMao2xiang(SchoolofTrafficandTransportation,Bei激ng激aotongUniversity,Bei激ng100044,China)Abstract:Onthebasisofintuitionisticdescriptionofthemulti2depotvehicleschedulingproblem,manymath2ematicmodelsoftheproblemisbuiltinthispaper.Thesolvingtacticsofdividingamulti2depotvehicleschedulingproblemintoseveralsingle2depotvehicleschedulingproblemsbyusingtheminimumdistancedistributionmethodispresented.Thealgorithmforthemulti2depotvehicleschedulingproblemisdesignedbasedonthetaboosearchal2gorithmforsingle2depotvehicleschedulingproblem.Thecomputationalresultsdemonstratesthatthehighqualitysolutionstothemulti2depotvehicleschedulingproblemcanbeobtainedbyusingthenewalgorithmandthealgo2rithmisalsoefficientandrobust.Keywords:multi2depotvehicleschedulingproblem;model;algorithmCLCnumber:U4910引言配送是现代化物流系统的一个重要环节,它是指按用户的订货要求,在配送中心进行分货、配货,并将配好的货物及时送交收货人.在配送业务中,存在许多优化决策问题,其中配送车辆调度问题对配送企业加快配送速度、提高服务质量、降低配送成本的影响较大.根据配送中心数目的多少,配送收稿日期:2006203209车辆调度问题有单配送中心车辆调度问题和多配送中心车辆调度问题之分.在城市物流体系中,往往存在多个配送中心.因此,对多配送中心车辆调度问题的研究具有重要的现实意义.现有对配送车辆调度问题的研究主要集中在单配送中心问题上,对多配送中心车辆调度问题的研究很少,国内对该问题的研究基本上是空白.国郎茂祥(1969-),男,山东高唐人,北京交通大学交通运输学院教授,博士,主要研究方向为交通运输规划与管理.Email:langmaoxiang@jtys.bjtu.edu66交通运输系统工程与信息2006年10月外的Renaud、Desaulniers、Wu、Kazaz、Sumichrast、Ir2nich等专家对多配送中心车辆调度问题进行了研中心),令rhk0=0表示配送中心,若以配送总里程最短为目标函数,则可建立如下多配送中心车辆调度问题的数学模型:minZ=Knhk究[1-6],并取得了一些有价值的研究成果.本文在现有研究成果的基础上,建立了多配送中心车辆调度问题的基于直观描述的数学模型,提出了采用距离最近分配法将多配送中心车辆调度问题分解为多个单配送中心车辆调度问题进行求解的策略,利用求解单配送中心车辆调度问题的禁忌搜索算法,设计了求解多配送中心车辆调度问题的算法,最后通过实验计算验证了该算法的良好性能.s.t.h=1666k=1Hhi=1drhk(i-1)rhki+drhknrhkhk0・sign(nhk)n(1)(2)ri=16hiqhrhki≤Qhkhkdrhk(i-1)rhki+drhkn≤sign(nhk)≤Dhk(3)(4)(5)(6)1多配送中心车辆调度问题的数学模型多配送中心车辆调度问题可以描述为:心的位置一定,,每一定,,能够满足所有客户的需求,要求合理安排车辆配送路线,使目标函数得到优化,并满足以下条件:①每条配送路径上各客户的需求量之和不超过车辆的载重量;②每条配送路径的长度不超过车辆一次配送的最大行驶距离;③每个客户的需求必须满足,且只能由一台车辆送货.设某城市中有H个配送中心,要给M个客户送货,每个配送中心服务的客户构成一个配送分区.设第h个配送中心要向Lh(h=1,2,…,H)个客户送货,第h个配送中心有Kh台配送车辆,每台车辆的载重量为Qhk(k=1,2,…,Kh),其一次配送的最大行驶距离为Dhk.第h个配送中心服务的第i个客户的货物需求量为qhi...