万方数据—VR唧、Dynamic物‘流配送车辆调度决策支持系统’勇，吴志勇，廖明，张战峰，赵鹏王型，采用交换插入算法⋯对区域之间车辆路径进行优1系统求解框架关键问题，也是组合优化领域的前沿与热点问题⋯．研究．例如，Fisher等提出了精确算法、Clarke和堍htmoolkit、MACS由于商业集团的配送是在用户数量多且分布密集度问题?针对该类问题的特点，笔者提出了一个三阶段合；2)建立车辆调度优化模型，利用启发式算法完成客户区域对车辆的分配；3)借助货郎担模型，采用交1．1客户区域化整合络配送的节点，因此在这里我们不做研究．这里主要是针对配送对象中的个人消费者而言，由于他们具有分第29卷第9期重庆大学学报(自然科学版)ChongqingUniverSity(NaturalEdition)文章编号：1000—582X(2006)09—0162—05摘要：基于交通条件、车辆承载能力等约束条件下，针对大规模车辆调度问题的特点，提出了三阶段一个求解框架．对大规模的客户群进行区域化整合．建立车辆调度优化模型，利用启发式算法完成客户区域对车辆的分配．借助货郎担模型，采用交换插入算法对区域之间车辆路径进行优化．最后利用该求解框架，以重庆某商业。集团为背景，设计和开发了物流配送决策支持系统．关键词：物流配送；车辆调度；决策支持系统中图分类号：U11．文献标识码：A在物流配送问题中，车辆调度问题(VsP)是一个为了解决这类问题，国内外的许多学者都对此进行了提出的节约法、Giuett和MiⅡer提出的扫描法以及J．H．Houand的遗传算法等口J．在国外，物流配送车辆调度系统的研究是从20世纪80年代中期发展起来的．其中主要有Geo—route、RouteGuidance和DRⅣE¨1．但是，国内在这方面的研究大多数停留在理论层次方面，实际开发和应用此类系统才刚刚起步．主要有：张思复和管仕平H】主要是在考虑了各网络节点需求不断变化的情况下提出了实时车辆调度系统；朱昌锋H1介绍了在物流配送车辆优化调度中如何应用地理信息系统(GIS)，利用图形、图象及数据处理技术增强系统的可视化；王平∞1介绍了邮政部门配送车辆调度系统的设计和开发的过程．然而以上文献所提到的方案都不够完善，只考虑了车辆调度规模比较小情况下的算法求解，且只是开发了配送系统的某一部分功能．万凤娇¨’虽然提出了开发配送调度系统的设想，但是没有进行具体的功能设计和算法求解．笔者在此基础上，提出了对于大规模车辆调度问题的一个三阶段求解框架：对大规模的客户群进行区域化整合；建立车辆调度优化模型，利用启发式算法完成客户区域对车辆的分配；借助货郎担模化；并且利用上述所提出的求解框架，以重庆某商业集团为背景，设计和开发了物流配送决策支持系统．情况下进行的，因此，车辆调度问题的规模大，依靠上述文献中的理论算法难以满意的解决大规模的车辆调求解框架：1)将大规模的客户群体进行区域化的整换插入算法对区域之间车辆路径进行优化．就商业集团的配送服务对象而言，主要是个体消费者和零售店．对于零售店的配送，由于其比较分散、配送量大、位置比较固定，可以将这些客户直接作为网布密度大、分布面广、数量多且每个客户的需求量非常小的特点，如果我们把这些客户直接作为网络配送的节点，问题研究的规模将十分庞大．2006年9月(重庆大学经济与工商管理学院，重庆4Cla忸O)·收稿日期：2006一04—02基金项目：重庆市自然科学基金(2004BB2180)；国家自然科学基金(70272028)；重庆大学研究生创新基金(2005】OY280310138)资助项目作者简介：王勇(1957一)，男，四川内江人，重庆大学教授，主要从事优化方法及在物流管理中的研究．JoumalofScienceSep．2006V01．29No．9FIeet—Manager、micro—AL，rO、Greentri万方数据∑‰∑却壮={m一，三冀^(3)i∑?=。∑是怖2{lf：l五，：一^∑二·∑却私2l㈨，2’3’!一，n，容积为以(矗=l，2，⋯，m)，单位距离行驶费用为c。(丘2决策支持系统开发区域以河流、铁路等屏障为界限再分成几部分，保证了=l，2⋯．，m)，所有客户的集合为．[0，l⋯．．，n)，其【oF=∑m-l∑?；o∑?：o(i一)c∥泄d口，∑?：o∑?：l石驻t，f≤K后=1，2，3，⋯，m，∑?：o∑冬l菇洳≤n约束条件(1)表示每辆车负责的客户点的货物需求量的总体积不超过该车辆最大容积；约束条件(2)距离略，然后算出车辆的后，行驶单位距离的费用C村；选出离车辆盂i配送的所有的任务中运输费用最大的车辆的忌，剩余容量减去任务t诰的货运量作为车蠡，新4)从待配送的客户区域中选出离车辆配送的所5)判断所有客户区域的任务是否都已经配送