物流配送系统中车辆路径问题应用研究

问题在学术研究和实际应用上产生了许多不同的延伸和变化型态,包括带有时间窗约束的车辆路径问题(Vehicle Routing Problems with Time Windows,VRPTW)、车辆可重复利用的车辆路径问题(Vehicle Routing Problems with Re.used ofVehicles,VRPRV)、考虑带回程的车辆路径问题(Vehicle Routing Problems with Backhauls,VRPB)、随机需求车辆路径问题(Vehicle Routing Problems with Stochastic Demand,VRPSD) 等等。 2.车辆路径问题求解方法研究综合有关车辆路径问题的求解方法,可以分为精确算法与启发式算法。l 995 年,Fisher曾将求解车辆路径问题的算法分成三个阶段。第一阶段是从1960年到1970年,属于简单启发式算法,包括有各种局部改善启发式算法和贪婪法(Greedy)等;第二阶段是从1970年到1980年,属于一种以数学规划为主的启发式解法,包括指派法、集合分割法和集合涵盖法;第三阶段是从1990开始至今,属于较新的方法,包括利用严谨启发式算法、人工智能方法等。由于VRP 是NP—hard问题,难以用精确算发求解,启发式算法是求解车辆路径问题的主要算法。 VRP问题是一种组合优化问题,由经典的TSP问题发展而来,已经广泛地运用于生产、生活的各个方面,如报纸投递的线路优化、牛奶配送及送达线路的优化、电话预订货物的车辆载货和线路设计、垃圾车的线路优化及垃圾站选址优化、连锁商店的送货及线路、机器人任务规划、热轧调度、卫星导航网络设计等等。 1.3AD物流公司现状 AD物流有限公司,创建于1996年,经过十几年的发展壮大,已在广州、顺德、中山等地注册分公司,现已经成为一家集汽车运输、仓储、配送、货代 3