一种带时间窗口和在前约束的车辆路线问题及其算法.pdf

　2000 年 3 月 系统工程理论与实践 第 3 期　 一种带时间窗口和在前约束的车辆路线问题及其算法 叶耀华, 朱晓梅, 陈　霖 ( 复旦大学管理学院, 上海 200433) 摘要: 　提出一种带时间窗口和在前约束的车辆路线问题(V RPTW PC ) , 并构造了求解该问题的一 种基于列生成的算法 快递收发路线编排是此类问题的一个典型例子 关键词: 　车辆路线问题; 在前约束; 列生成 中图分类号: 　 221 1; 1141　　 O TB T he V eh icle Rou ting P rob lem w ith T im e W indow s and P recedence Con strain ts and Its A lgo rithm , , YE Yao hua ZHU X iao m ei CH EN L in (Schoo l of M anagem ent, Fudan U niversity, Shanghai 200433) Abstract: 　T h is paper p resents the veh icle routing p roblem w ith tim e w indow s and . . p recedence constraints W e also p ropo se an algo rithm based on co lum n generation O ne of the typ ical cases of th is p roblem is how to arrange the routes of the exp ress p ick up . and delivery Keywords: 　veh icle routing p roblem ; p recedence constraints; co lum n generation 1　引言 车辆路线问题(the V eh icle Routing P roblem , V R P ) 是求一组总路程最短的车辆路线, 所有这些车辆 路线的起点和终点均为中心点, 车辆的容量也相同, 并且到达每个客户点至少一次且仅仅一次 带时间窗 口车辆路线问题(the V eh icle Routing P roblem w ith T im e W indow s, V R PTW ) 是求一组满足上述条件和 目标, 并且对每个客户开始服务的时间都要在一定的时间窗口内的车辆路线 [1 ] M artin D esrochers 等人于 1992 年提出了V R PTW 的一种基于列生成的算法 , 这种算法是目前 V R PTW 的几种主要求解方法之一[2 ] 带时间窗口和在前约束的车辆路线问题 (T he V eh icle Routing P