【作者】 刘霞；

【导师】 齐欢；

【作者基本信息】 华中科技大学 ， 系统工程， 2007， 博士

【摘要】 随着经济全球化和信息化进程的不断加快,物流作为具有广阔前景和增值功能的新兴服务业,正在全球范围内迅速发展,它对于提高国家经济运行质量和效益、优化资源配置、增强企业竞争力和促进企业生产力的发展具有重要意义。运输服务是物流组成中的重要环节,降低运输成本、提高运输质量和效率成为加快物流发展的有效途径。车辆路径问题是运输服务优化中的核心问题,它通过对货物的运输线路进行优化,在满足客户需求的前提下,尽量以最低的运输成本将货物送达目的地。在过去几十年间,车辆路径问题得到了广泛的关注和研究,并取得了丰富的研究成果。本文首先对这类问题的构成、分类以及求解算法的研究现状等进行了归纳和概括。最小-最大车辆路径问题,是与一般车辆路径问题目标不同的一类问题,它要求在整个行车线路中,行程最长的线路行驶距离最短。本文根据这类问题的特点,采用遗传算法和禁忌搜索算法进行了求解。并在禁忌搜索算法中,针对最长的线路生成邻域,将该算法用于标准算例的求解,得到了较好的结果。在实际的线路计划和执行过程中,往往会出现新的客户请求或客户信息的变化,这时要求系统能快速响应这种信息更新,并重新制定线路计划。这类问题称为动态车辆路径问题。对于基本的动态车辆路径问题,本文研究了相应的处理策略,分析了系统的基本组成,将整个动态问题转换为一系列的静态子问题,对子问题采用禁忌搜索算法进行求解。以整个线路的行驶距离作为目标,采用该算法对9个标准算例进行了测试,与文献中其他算法的计算结果相比较,有3个问题得到了最好解,7个问题得到了最好平均解。由于交通管制和客户营业时间等实际约束,某些客户只能在某些时间段接受车辆为其提供的服务,即客户有时间窗限制,本文在带时间窗的动态车辆路径问题中,分析了三种线路间局部搜索方法:重定位法,节点交换法和2-opt*法,以及两种线路内局部搜索方法:2-opt法和Or-opt法,并将这些方法的不同组合应用于静态子问题初始解的改进。通过对标准算例的求解结果进行分析和比较得出:在线路间进行局部搜索时,重定位法的效果最好,2-opt*法次之,节点交换法的最差;在线路内进行局部搜索时,2-opt法优于Or-opt法。同时,也分析了客户出现时间的早晚,客户地理位置的分布以及不同的客户时间窗范围对结果线路中使用的车辆数量,整个线路的行驶距离和客户延迟时间的影响。在带时间窗的动态收取和运送问题中,要求从某一客户的收取点提取货物,送到其相应的运送点。因此要求同一客户的收取点和运送点必须由同一台车辆来执行服务,且必须在访问运送点之前先访问提取点。本文在描述该问题特点的基础上,采用了启发式方法对该问题进行求解,并对基本算例进行了测试。更多还原

【Abstract】 With rapid development of economic globalization and information technology, logistics has become a new value-added service industry with broad prospect. It is significant to improve operation quality and performance of national economic, optimize resource allocation, enhance competitiveness of enterprises and promote development of productivity. Being an important link in logistics, transportation service is an effective way to accelerate the development of logistics by reducing transportation cost, improving transportation quality and raising transportation efficiency.Vehicle routing problem is a key problem in the optimization of transportation service, it delivery goods to the destination at lowest cost in the premise of satisfying demand of customers. During the past decades, vehicle routing problem has been paid much attention to and many research results have been obtained. The composition and classification of vehicle routing problem are introduced, and the present situation of algorithms is generalized.The objective of min-max vehicle routing problem is to minimize travelling distance of the longest route among all routes, so it is different with common vehicle routing problem. Genetic algorithm and tabu search are adopted to solve these problems. Neighbors are created with focus on the longest route in tabu search. Tests are performed on standard instances and good results are found.In the course of practical route planning and performing, new customer requests may arrive or information may change. A quick response must be made to the updated information and routes should be re-planned. This kind of problem is called dynamic vehicle routing problem. Treatment strategies are studied and system composition are analyzed for basic dynamic vehicle routing problem, and then dynamic problem are partitioned into a series of static sub-problems, which is solved by tabu search. Instances are tested with the objective to minimize total travelling distance of all routes. Compared with results obtained by other algorithms in literature, three best solutions and seven best average solutions have been found among nine instances by tabu search. Due to actual restrictions such as traffic control and customers business hours, some customers accept service by vehicle only at some time intervals, which is called time window limit. Three inter-route local search approaches including relocation, exchange and 2-opt*, and two intra-route local search approaches including 2-opt and or-opt are introduced. Combination of different approaches is adopted to solve static sub-problems. Results of test instances show that relocation is the best, 2-opt* second and exchange the worst for inter-route local search, and 2-opt is better than or-opt for intra-route local search. Effects of arrival time, distribution of geography location and time-window range on vehicle number, traveling distance and delay of all routes are also analyzed.In dynamic pickup and delivery problem with time window, the vehicle should pick up goods at pickup location and then transport the goods to the delivery location, so the pickup location of a customer must be visited before its delivery location by the same vehicle. Characteristics are described and heuristics are introduced to solve this problem. Finally basic instances are used for tests.更多还原