标题: | 应用时窗离散策略与可回溯式门槛接受法求解VRPBTW问题之研究 Time Window Discretization and BATA Heuristics for Solving the VRPBTW Problems |
作者: | 陈仲豪 韩复华 运输与物流管理学系 |
关键字: | 时窗离散化;门槛接受法;可回溯式门槛接受法;回程取货车辆路线问题;具时窗限制之回程取货车辆路线问题;Time Window Discretization;Threshold Accepting (TA);Backtrack Adaptive Threshold Accepting (BATA);Vehicle Routing Problem with Backhauls (VRPB);Vehicle Routing Problem with Backhauls and Time Windows (VRPBTW) |
公开日期: | 2007 |
摘要: | 具时窗限制之回程取货车辆路线问题(Vehicle Routing Problem with Backhauls and Time Windows, VRPBTW)为传统车辆路线问题所发展出的相关问题,其假设车辆必须先服务完所有送货点顾客,然后才能开始服务取货点顾客,且所有顾客皆有时间窗之限制,求解复杂度相当高,属于NP-Hard问题。 本研究应用时窗离散策略与可回溯式门槛接受法求解VRPBTW问题,研究方法分为两阶段进行。第一阶段采取时间窗离散化(Time Window Discretization)的方法,将VRPBTW问题中的时间窗限制消除,转换成无时间窗的VRPB问题,并根据VRPBTW问题特性设计问题规模精简策略,缩小问题规模。第二阶段求解转换后的VRPB问题,首先以最近邻点法构建起始解,采用Reduction、1-0、1-1、S-S及Or-opt等邻域搜寻法进行改善,并且应用可回溯式门槛接受法(Backtracking Adaptive Threshold Accepting, BATA)做为求解VRPB问题之巨集启发式解法架构。 本研究以Gelinas et al. (1995)的15题国际标竿例题做为测试例题,利用C#语言撰写程式,在Intel(R)双核心,CPU为2.00GHz的个人电脑进行测试。结果发现,本研究第一阶段所采用之五项问题规模精简策略可有效地简化转换后无时窗的VRPB问题规模。15题标竿例题中,节点总数平均减少15.3%,节线总数平均减少97.3%。在第二阶段本研究设计之BATA模组测试中,15题标竿例题之最佳结果,车辆数平均误差为0.87辆,且有5题找到文献已知最佳结果;旅行成本平均误差为5.32%。本研究亦发现,在标竿题库BHR101题组中,车辆数均能找到已知最佳结果,显示结合时窗离散策略与可回溯式门槛接受法进行求解,对于原作业点时间窗宽度较小且均匀的问题,求解效果较佳。 Vehicle Routing Problem with Backhauls and Time Windows (VRPBTW), an extension of the classical Vehicle Routing Problem, is a very complicated NP-Hard problem. The VRPBTW assumes that all linehaul customers should be visited before any backhaul customer, and all customers need to be visited within a specific time window. In this thesis, we proposed a two-phase approach to solve the VRPBTW problems. In the first phase, we transformed the VRPBTW problems to approximate VRPB problems, removing the time window constraints from the original problems. We also proposed Problem Scale Simplification Strategy to reduce the size of the transformed VRPB problems. The second phase is focused on solving the transformed VRPB problems using a meta-heuristic approach. A feasible initial solution was first generated by Nearest Neighbor algorithm, and improved by neighborhood search methods such as Reduction, 1-0, 1-1, S-S, Or-opt. We then applied Backtracking Adaptive Threshold Accepting (BATA) to further improve the solutions. The 15 benchmark problems described by Gelinas et al. (1995) were selected for the evaluation of our meta-heuristics. Our proposed heuristics were coded in Visual C# and tested on a Intel(R) Core(TM)2 CPU 2.00GHz personal computer. We found that our proposed Problem Scale Simplification Strategy can effectively reduce the number of nodes and arcs by 15.3% and 97.3% respectively on average. Results showed that for the 15 benchmark problems, the average deviation from the best known solutions are 0.87 in fleet size, and 5.32% in total distance respectively. We also found five best known solutions of the 15 VRPBTW benchmarks. The results of our study implied that our proposed time window discretization approach is most effective for solving VRPBTW problems with uniform and relatively small time windows. |
URI: | http://140.113.39.130/cdrfb3/record/nctu/#GT009532523 http://hdl.handle.net/11536/39123 |
显示于类别: | Thesis |
文件中的档案:
If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.