论文部分内容阅读
物流配送是物流活动中直接与消费者相连的环节。在物流的各项成本中,配送成本占了相当高的比例。配送车辆优化调度管理的合理与否对配送速度、成本、效益影响很大,是物流配送中非常重要的一项活动。车辆优化调度问题一般可根据空间特性和时间特性分为车辆线路规划问题和车辆调度问题。当不考虑时间要求,仅根据空间位置安排车辆的线路时称为车辆线路或车辆路径规划问题(VRP——Vehicle Routing Problem);当考虑时间要求安排运输线路时称为车辆调度问题VSP(VSP--Vehicle Scheduling Problem)。某些学者将有时间要求的车辆路径规划问题称为Vehicle Routing Problem with Time Windows(VRPTW)。 本文以“济南烟草集团现代化物流配送系统”为研究和实践背景,在对现有配送车辆线路优化问题(VRP)算法归类分析和对企业实际业务要求提炼基础上,考虑城市街道中方向性和具体路况等因素,将城市配送用户数量非常多的大规模VRP问题分解为两个求解过程:首先,进行配送线路区域划分,对于烟草行业城市销售网点超过1万个甚至是几万个网点的情况下将配送线路划分为几个物理区域,是考虑计算机运行效率行之有效的方法;其次,在每个已划分的区域中进行单车线路优化即TSP(Traveling Salesman Problem,旅行商问题)问题的求解。通过以上两个过程可以较好地解决大规模配送网点情况下要在计算机运行效率能满足用户要求的时间内求得VRP这类NP-hard问题最优或较优解的矛盾。这种方法对一个配送中心,但配送网点数目极大的配送车辆线路优化问题具有普适性。 本文主要以VRP车辆线路优化运筹学理论为指导,重点运用启发式VRP算法,包括节约里程和改进的节约时程算法、先分组后单车线路优化的二阶段方法以及带软时间窗(即用户对时间要求不是非常苛刻而是任务只要在某段时间内完成即可的配送方式)和车辆配载能力的VRP模型。对城市真实道路建立基于GIS系统的配送网点、关键点的道路信息库,并运用最短路径Dijkstra算法求解任意两点之