Pickup and delivery problems (PDPs) have been studied extensively in past decades. A wide variety of research exits on both exact algorithms and heuristics for generic variations of the problem as well as real-life applications, which continue to spark new challenges and open up new opportunities for researchers. In this dissertation, we study two variations of pickup and delivery problem that arise in industry and develop new computational methods that are shown to be effective with respect to existing algorithms and scheduling procedures found in practice. The first problem is the pickup and delivery problem with transshipment (PDPT). The work presented here was inspired by a daily route planning problem at a regional air carrier. In structuring the analysis, we describe a unique way to model the transshipment option on a directed graph. With the graph as the foundation, we implemented a branch and price algorithm. Preliminary results showed that it has difficulty in solving large instances. As an alternative, we developed a greedy randomized adaptive search procedure (GRASP) with several novel features. In the construction phase, shipment requests are inserted into routes until all demand is satisfied or no feasible insertion exists. In the improvement phase, an adaptive large neighborhood search algorithm is used to reconstruct portions of the feasible routes. Specialized removal and insertion heuristics were designed for this purpose. We also developed a procedure for generating problem instances in the absence of any in the literature. Testing was done on existing PDP data sets and generated PDPT data set. For the former, the performance and solution quality of the GRASP were comparable to the best known heuristics. For the latter, GRASP found the near optimal solution in most test cases. In the second part of the dissertation, we focus on a new version of the heterogeneous PDP in which the capacity of each vehicle can be modified by reconfiguring its interior to satisfy different types of customer demands. The work was motivated by a daily route planning problem arising at a senior activity center. A fleet of configurable vans is available each day to transport participants to and from the center as well as to secondary facilities for rehabilitative and medical treatment. To find solutions, we developed a two-phase heuristic that makes use of ideas from greedy randomized adaptive search procedures with multiple starts. In phase I, a set of good feasible solutions is constructed using a series of randomized procedures. A representative subset of those solutions is selected as candidates for improvement by solving a max diversity problem. In phase II, an adaptive large neighborhood search (ALNS) heuristic is used to find local optima by reconstructing portions of the feasible routes. Also, a specialized route feasibility check with vehicle type reassignment is introduced to take full advantage of the heterogeneous nature of vehicles. The effectiveness of the proposed methodology is demonstrated by comparing the solutions it provided for the equivalent of several weeks with those that were used in practice and derived manually. The analysis indicates that anywhere from 30% to 40% savings can be achieved with the multi-start ALNS heuristic. An exact method is introduced based on branch and price and cut for settings with more restricted time windows. In the procedure, the master problem at each node in the search tree is solved by column generation to find a lower bound. To improve the bound, subset-row inequalities are applied to the variables of the master problem. Columns are generated by solving the pricing subproblems with a labeling algorithm enhanced by new dominance conditions. Local search on the columns is used to quickly find promising alternatives. Implementation details and ways to improve the performance of the overall procedure are discussed. Testing was done on a set of real instances as well as a set of randomly generated instances with up to 50 customer requests. The results show that optimal solutions are obtained in majority of cases. / text

京都大学 / 新制・課程博士 / 博士(工学) / 甲第24219号 / 工博第5047号 / 新制||工||1788(附属図書館) / 京都大学大学院工学研究科都市社会工学専攻 / (主査)教授 藤井 聡, 教授 山田 忠史, 准教授 QURESHI Ali Gul / 学位規則第4条第1項該当 / Doctor of Philosophy (Engineering) / Kyoto University / DGAM