In this paper, we introduce two algorithms to address the two-echelon capacitated location-routing problem (2E-CLRP). We introduce a branch-and-cut algorithm based on the solution of a new two-index vehicle-flow formulation, which is strengthened with several families of valid inequalities. We also propose an adaptive large-neighbourhood search (ALNS) meta-heuristic with the objective of finding good-quality solutions quickly. The computational results on a large set of instances from the literature show that the ALNS outperforms existing heuristics. Furthermore, the branch-and-cut method provides tight lower bounds and is able to solve small- and medium-size instances to optimality within reasonable computing times.

In this paper,we propose an adaptive large neighborhood search heuristic for the Two-Echelon Vehicle Routing Problem (2E-VRP) and the Location Routing Problem (LRP).The 2E-VRP arises in two-level transportation systems such as those encountered in the context of city logistics. In such systems, freight arrives at a major terminal and is shipped through intermediate satellite facilities to the final customers. The LRP can be seen as a special case of the 2E-VRP in which vehicle routing is performed only at the second level. We have developed new neighborhood search operators by exploiting the structure of the two problem classes considered and have also adapted existing operators from the literature. The operators are used in a hierarchical scheme reflecting the multi-level nature of the problem. Computational experiments conducted on several sets of instances from the literature show that our algorithm out performs existing solution methods for the 2E-VRP and achieves excellent results on the LRP.

京都大学 / 0048 / 新制・課程博士 / 博士(工学) / 甲第19287号 / 工博第4084号 / 新制||工||1630(附属図書館) / 32289 / 京都大学大学院工学研究科都市社会工学専攻 / (主査)教授 谷口 栄一, 教授 藤井 聡, 准教授 宇野 伸宏 / 学位規則第4条第1項該当 / Doctor of Philosophy (Engineering) / Kyoto University / DFAM

Missed deliveries are a major issue for package carriers and a source of great hassle for the customers. Either the carrier attempts to redeliver the package, incurring the additional expense of visiting the same house up to three times, or they leave the package on the doorstep, vulnerable to package thieves. In this dissertation, a system of collection-and-delivery-points (CDPs) has been proposed to improve customer service and reduce carrier costs. A CDP is a place, either in an existing business or a new location, where the carrier drops any missed deliveries and the customers can pick the packages at their convenience. To examine the viability of a CDP system in North America, a variation on a location-routing problem (LRP) was created, a mixed-integer programming model called the CDP-LRP. Unlike standard LRPs, the CDP-LRP takes into account both the delivery truck route distance and the direct customer travel to the CDPs. Also, the facilities being placed are not located at the beginning and ending of the truck routes, but are stops along the routes. After testing, it became clear that, because of the size and complexity of the problem, the CDP-LRP is unable to be solved exactly in a reasonable amount of time. Heuristics developed for the standard LRP cannot be applied to the CDP-LRP because of the differences between the models. Therefore, three heuristics were created to approximate the solution to the CDP-LRP, each with two different embedded modified vehicle routing problem (VRP) algorithms, the Clark-Wright and the Sweep, modified to handle the additional restrictions caused by the CDPs. The first is an improvement heuristic, in which each closed CDP is tested as a replacement for each open CDP, and the move that creates the most savings is implemented. The second begins with every CDP open, and closes them one at a time, while the third does the reverse and begins will only one open CDP, then opens the others one by one. In each case, a penalty is applied if the customer travel distance is too long. Each heuristic was tested for each possible number of open CDPs, and the least expensive was chosen as the best solution. Each heuristic and VRP algorithm combination was tested using three delivery failure rates and different data sets: three small data sets pulled from VRP literature, and randomly generated clustered and uniformly distributed data sets with three different numbers of customers. OpenAll and OpenOne produced better solutions than Replacement in most instances, and the Sweep Algorithm outperformed the Clark-Wright in both solution quality and time in almost every test. To judge the quality of the heuristic solutions, the results were compared to the results of a simple locate-first, route-second sequential algorithm that represents the way the decision would commonly be made in industry today. The CDPs were located using a simple facility location model, then the delivery routes were created with the Sweep algorithm. These results were mixed: for the uniformly distributed data sets, if the customer travel penalty threshold and customer density are low enough, the heuristics outperform the sequential algorithm. For the clustered data sets, the sequential algorithm produces solutions as good as or slightly better than the sequential algorithm, because the location of the potential CDP inside the clusters means that the penalty has less impact, and the addition of more open CDPs has less effect on the delivery route distances. The heuristic solutions were also compared to a second value – the route costs incurred by the carrier in the current system of redeliveries, calculated by placing additional customers in the routes and running the Sweep algorithm – to judge the potential savings that could be realized by implementing a CDP system in North America. Though in some circumstances the current system is less expensive, depending on the geographic distribution of the customers and the delivery failure rate, in other circumstances the cost savings to the carrier could be as high as 27.1%. Though the decision of whether or not to set up a CDP system in an area would need to be made on a case-by-case basis, the results of this study suggest that such a system could be successful in North America. / Doctor of Philosophy / Missed deliveries are a major issue for package carriers and a source of great hassle for the customers. Either the carrier attempts to redeliver the package, incurring the additional expense of visiting the same house up to three times, or they leave the package on the doorstep, vulnerable to package thieves. In this dissertation, a system of collection-and-delivery-points (CDPs) has been proposed to improve customer service and reduce carrier costs. A CDP is a place, either in an existing business or a new location, where the carrier drops any missed deliveries and the customers can pick the packages at their convenience. To examine the viability of a CDP system in North America, a mathematical programming model was created called the CDP-LRP. Because of the size and complexity of the problem, it is unable to be solved exactly in a reasonable amount of time. Therefore, three heuristics were created to approximate the solution to the CDP-LRP, each with two different embedded modified vehicle routing problem (VRP) algorithms. For all the heuristics, a penalty is applied if the customer travel distance is too long. Each heuristic and VRP algorithm combination was tested using different data sets: three small data sets pulled from VRP literature, and randomly generated clustered and uniformly distributed data sets with three different numbers of customers. To judge the quality of the heuristic solutions, the results were compared to the results of a simple locate-first, route-second sequential algorithm that represents the way the decision would commonly be made in industry today. These results were mixed: for the uniformly distributed data sets, if the customer travel penalty threshold and customer density are low enough, the heuristics outperform the sequential algorithm. For the clustered data sets, the sequential algorithm produces solutions as good as or slightly better than the sequential algorithm, because the location of the potential CDP inside the clusters means that the penalty has less impact, and the addition of more open CDPs has less effect on the delivery route distances. The heuristic solutions were also compared to a second value – the route costs incurred by the carrier in the current system of redeliveries – to judge the potential savings that could be realized by implementing a CDP system in North America. Though in some circumstances the current system is less expensive, depending on the geographic distribution of the customers and the delivery failure rate, in other circumstances the cost savings to the carrier could be as high as 27.1%. Though the decision of whether or not to set up a CDP system in an area would need to be made on a case-by-case basis, the results of this study suggest that such a system could be successful in North America.

As localizações dos terminais e as rotas de entrega que partem desses terminais são decisões importantes que surgem na concepção de redes de transporte de carga fracionada. Nesses casos, dois problemas independentes precisam ser tratados: o problema da localização de instalações (LAP) e o problema da roteirização dos veículos (VRP). Este trabalho apresenta um modelo matemático para resolver o LAP e o VRP de forma integrada, ou seja, para a resolução do problema de Localização/Roteirização (Location Routing Problem - LRP). De acordo com a literatura, a abordagem integrada do LRP fornece melhores resultados do que a solução do LAP e do VRP separadamente. O modelo foi testado e aplicado em um caso real de Many-to-Many com Multiplos elos LRP, respeitou as restrições e o nível de serviço exigido e propiciou melhoria nos resultados para a empresa de transporte no qual foi aplicado. Os resultados do modelo também foram melhores do que os resultados apresentados por um software líder de mercado. / In the Less Than Truck Load (LTL) operations both the location of facilities and the routing of vehicles are important decisions for the optimal design of the related logistics network. Two interdependent problems arise: the Location Allocation Problem (LAP) and the Vehicle Routing Problem (VRP). This paper presents a mathematical model to solve the LAP and the VRP simultaneously on an integrated way, such as the so-called Location-Routing Problem (LRP). According to the literature the LRP integrated approach provides better results than considering the LAP and the VRP separately. The model was tested and applied to a real case of Many-to-Many with Multi-Echelons LTL Location-Routing Problem respecting the constraints and the required service level standard and provided better results for the company in which it was tested. The model results also were better than the results presented by market-leading software.

As localizações dos terminais e as rotas de entrega que partem desses terminais são decisões importantes que surgem na concepção de redes de transporte de carga fracionada. Nesses casos, dois problemas independentes precisam ser tratados: o problema da localização de instalações (LAP) e o problema da roteirização dos veículos (VRP). Este trabalho apresenta um modelo matemático para resolver o LAP e o VRP de forma integrada, ou seja, para a resolução do problema de Localização/Roteirização (Location Routing Problem - LRP). De acordo com a literatura, a abordagem integrada do LRP fornece melhores resultados do que a solução do LAP e do VRP separadamente. O modelo foi testado e aplicado em um caso real de Many-to-Many com Multiplos elos LRP, respeitou as restrições e o nível de serviço exigido e propiciou melhoria nos resultados para a empresa de transporte no qual foi aplicado. Os resultados do modelo também foram melhores do que os resultados apresentados por um software líder de mercado. / In the Less Than Truck Load (LTL) operations both the location of facilities and the routing of vehicles are important decisions for the optimal design of the related logistics network. Two interdependent problems arise: the Location Allocation Problem (LAP) and the Vehicle Routing Problem (VRP). This paper presents a mathematical model to solve the LAP and the VRP simultaneously on an integrated way, such as the so-called Location-Routing Problem (LRP). According to the literature the LRP integrated approach provides better results than considering the LAP and the VRP separately. The model was tested and applied to a real case of Many-to-Many with Multi-Echelons LTL Location-Routing Problem respecting the constraints and the required service level standard and provided better results for the company in which it was tested. The model results also were better than the results presented by market-leading software.

This study deals with a municipal solid waste management system in which the strategic and tactical decisions are addressed simultaneously. In the system, the number and locations of the transfer facilities which serve to the particular solid waste pick-up points and the landfill are determined. Additionally, routing plans are constructed for the vehicles which collect the solid waste from the pick-up points by regarding the load capacity of the vehicles and shift time restrictions. We formulate this reverse logistics system as a location-routing problem with two facility layers. Mathematical models of the problem are presented, and an iterative capacitated-k-medoids clustering-based heuristic method is proposed for the solution of the problem. Also, a sequential clustering-based heuristic method is presented as a benchmark to the iterative method. Computational studies are performed for both methods on the problem instances including up to 1000 pick-up points, 5 alternative transfer facility sites, and 25 vehicles. The results obtained show that the iterative clustering-based method developed achieves considerable improvement over the sequential clustering-based method.

This thesis deals with stochastic location routing problem. Multiple stochas- tic and deterministic models are formulated and it is discussed that it is difficult to solve these problems via exact integer programming methods. It is necessary to develop heuristic methods to find a solution of these problems. Multiple ver- sions of these problems are formulated and their properties and possibilities how to solve them are discussed. Therefore, the brand new Blockchain metaheuristic is developed and later used for solving stochastic location routing problem ap- plied on a waste collection problem. As a part of Blockchain metaheuristic we develop the new application of Greedy algorihtm that is used for finding initial solution. The quality of the heuristic algorithm developed by us is presented in a numerical study. 1

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

Submitted by Liliane Ferreira (ljuvencia30@gmail.com) on 2018-03-08T14:57:43Z No. of bitstreams: 2 Dissertação - Kamyla Maria Ferreira - 2018.pdf: 2406020 bytes, checksum: 87a4f31f5a394055dd9a84a1c7c73512 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2018-03-12T11:16:50Z (GMT) No. of bitstreams: 2 Dissertação - Kamyla Maria Ferreira - 2018.pdf: 2406020 bytes, checksum: 87a4f31f5a394055dd9a84a1c7c73512 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2018-03-12T11:16:50Z (GMT). No. of bitstreams: 2 Dissertação - Kamyla Maria Ferreira - 2018.pdf: 2406020 bytes, checksum: 87a4f31f5a394055dd9a84a1c7c73512 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2018-02-16 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / This research deals with the resolution of problems that involve the location, routing, and packing decisions with focus on the location routing problem, capacitated vehicle routing problem with two-dimensional loading constraints, and location routing problem with two-dimensional loading constraints. For that, it is proposed a framework that reuses part of the algorithms, which are of a common domain, such that the development of the project is systematized. The objective of the framework is allowing the resolution of different variants of problems that integrate location, routing, and packing decisions without the need to replicate algorithms. As a proposal for an algorithm, it is developed a hybrid heuristic, which involves the cooperation between the simulated annealing and the artificial algae algorithm. The simulated annealing has four neighborhood operators, local search, and three procedures to diversify the solution. The artificial algae algorithm is combined with the skyline method in order to verify the feasibility of the two-dimensional packing constraints. Once the framework and heuristics have been codified, computational experiments are performed to test its performance, as well as comparisons are made with the most recent results published in the literature. The results show that the heuristic is competitive with other methods from the literature since it could obtain 36.25% solutions equal to the best ones reported in the literature of the location routing problem, besides the average GAP being 0.57%. For the vehicle routing problem with two-dimensional loading constraints, the heuristic could obtain 43.05% solutions equal to the best known in the literature, besides the average GAP being 3.33%. The results obtained for the location routing problem with twodimensional loading constraints were satisfactory. / Este trabalho trata da resolução de problemas que envolvem decisões de localização, roteamento e empacotamento com foco nos problemas de localização e roteamento, roteamento de veículos capacitado com restrições de empacotamento bidimensional, e localização e roteamento com restrições de empacotamento bidimensional. Para tanto, propõe-se um framework capaz de reutilizar parte dos algoritmos, que são de domínio comum, para que o desenvolvimento do projeto seja sistematizado. O objetivo é que o framework possibilite a resolução de diferentes variantes do problema que integram as decisões de localização, roteamento e empacotamento sem ter que replicar algoritmos. Como proposta de algoritmo, desenvolve-se uma heurística híbrida, a qual envolve a cooperação entre dois métodos, o recozimento simulado e o algoritmo artificial de algas. O recozimento simulado possui quatro operadores de vizinhança, procedimentos de busca local e três procedimentos para diversificar a solução. O algoritmo artificial de algas é combinado com a técnica Skyline para verificar as restrições de empacotamento bidimensional. A partir da codificação do framework e da heurística, experimentos computacionais foram realizados para testar o seu desempenho e comparar os resultados com os mais recentes da literatura. Os resultados indicam que a heurística é competitiva com os demais métodos da literatura, sendo possível obter 36,25% de soluções iguais às melhores reportadas na literatura do problema de localização e roteamento, além do GAP médio ter sido de 0,57%. No problema de roteamento de veículos com restrições de empacotamento bidimensional, a heurística obteve 43,05% soluções iguais às melhores conhecidas na literatura, além do GAP médio ter sido de 3,33%. Os resultados obtidos para o problema de localização e roteamento com restrições de empacotamento bidimensional foram satisfatórios.