Motivated by collaborative recycling efforts for non-profit agencies, we study a variant of the periodic location routing problem, in which one decides the set of open depots from the customer set, the capacity of open depots, and the visit frequency to nodes, in an effort to design networks for collaborative pickup activities. We formulate this problem, highlighting the challenges introduced by these decisions. We examine the relative dfficulty introduced with each decision through exact solutions and a heuristic approach which can incorporate extensions of model constraints and solve larger instances. The work is motivated by a project with a network of hunger relief agencies (e.g., food pantries, soup kitchens and shelters) focusing on collaborative approaches to address their cardboard recycling challenges collectively. We present a case study based on data from the network. In this novel setting, we evaluate collaboration in terms of participation levels and cost impact. These insights can be generalized to other networks of organizations that may consider pooling resources.

We propose a large neighborhood search (LNS) algorithm to solve the periodic location routing problem (PLRP). The PLRP combines location and routing decisions over a planning horizon in which customers require visits according to a given frequency and the specific visit days can be chosen. We use parallelization strategies that can exploit the availability of multiple processors. The computational results show that the algorithms obtain better results than previous solution methods on a set of standard benchmark instances from the literature.

The most common decisions to be taken in the design of logistic systems are related to the location of facilities and the management of vehicle fleets.In this thesis, we study three of the optimization problems arising around this kind of decisions; namely the LRP, the SGAP and the SLRP. The first problem analyzed in this work is a capacitated LRP with one single uncapacitated vehicle at each open plant. To model this problem we resort to an auxiliary network that allows us to represent feasible solutions as families of paths satisfying a series of side constraints.The solutions of a reinforced LP relaxation of this model are used as the basis of a rounding heuristic designed to build feasible solutions of the problem. Those solutions are then improved with a TS heuristic.Two lower bounds, distinct from that obtained with the LP relaxation of the model, are proposed for this problem. The first one is obtained by bound ing separately the two different parts of the cost of any feasible solution, namely the fixed costs for opening plants and the route costs. The second lower bound is the result of applying CG to the Lagrangian dual obtained by dualizing the assignment constraints. The pricing problem obtained from our formulation is an ESPPRC. The complexity of this problem, and the fact that optimality of the obtained solutions is not always necessary, have motivated us to develope a simple heuristic for it.The computational experiences show a very good behavior of the TS procedure both, for the computational effort required and the quality of the solutions. The first lower bound proposed gives satisfactory results in reasonable amounts of time. In the case of the CG approach, results are very encouraging. In some of the tested instances the program terminated because of the CPU time limit specification, before succeeding to find a valid lower bound.In those instances, the algorithm was always stalled in the exact resolution of an ESPPRC. The difficulties encountered to solve this problem represent a limitation of this approach and suggest the future study of alternative solution methods. In spite of this limitation, in a high proportion of the instances the algorithm succeeded, and the final gap between the upper and the lower bound was always 0. The success in these instances is partially due to the use of our heuristic to generate new columns whenever this is possible.The second problem studied in this thesis is a SGAP. In this assignment problem the jobs are interpreted as customers that can request a service with a given probability, and each agent can serve a limited number of customers. This uncertainty about the presence of each customer is represented by modelling the demands of the customers as Bernoulli distributed independent random variables. The problem consists of finding an a priori assignment of customers to agents. Once the actual requests for service are known, an adaptive action is taken to tackle violations of the capacity constraints. On the one hand, part of the customers assigned to overloaded agents can be reassigned. On the other hand, some of the service requests can be disregarded. Different penalties for reassignment and for unattended service requests are pre-specified. The problem is formulated as a recourse model, where the recourse function gives the expected penalties for reassignments and unattended service requests.Since this recourse function is defined as the expected value of an integer programming recourse model, it does not have the regularity properties characteristic of those defined by linear recourse models. To overcome the difficulties caused by this, we construct a convex approximation of the recourse function that is tight in all feasible points. Moreover, as illustrated in the computational experiences, the use of this approximation reduces the computational effort required to evaluate the recourse function is some orders of magnitude. The convex approximation of the recourse function allows us to adapt the well-known L-shaped method to our problem. Integrality of the first stage variables is tackled in three different ways, giving raise to three versions of the algorithm. The difference among them resides in the hierarchy between the branching and the addition of violated cuts. On the one hand, we present a version where cuts are only added when integer solutions are found. On the other hand, a version is proposed where branching is only performed when no more violated cuts can be identified. The remaining version is designed as a tradeoff of these two; at each node of the search tree, new optimality cuts are added, if needed, and branching is performed if the solution at hand is fractional. Computational experiences point out this last version as the best of the three, since the efforts devoted to obtain a rich approximation of the recourse function and to achieve integrality are more balanced.We have also derived both, lower and upper bounds for this specific SGAP. Upper bounds are obtained from three simple heuristics. All them are based on solving deterministic approximations of the SGAP and provide good quality solutions in small amounts of CPU time. A lower bound is derived from a family of linear stochastic subproblems. Althoug in some of the tested instances the gap between the bounds exceeded the 30%, in the general case we obtained small gaps.One of the heuristics was used in the exact algorithm to provide it with a good upper bound. The lower bound is also used in the three versions of the algorithm, as the basis of some of the optimality cuts and also to identify optimal solutions. The quality of these bounds is one of the factors that explain the success of the exact algorithm.The last problem studied in this thesis is a SLRP. The stochasticity considered here is of the same type as that considered for the SGAP. Again, customers may request a service with a given probability and this is modeled by introducing Bernoulli random variables to represent the demands. A two stage model is proposed for this problem. In a first stage, a set of plants to open has to be chosen together with a family of disjoint routes (one rooted at each open plant) that visit all the customers. In the second stage, once all the demands become available, the actual routes have to be designed. For plants whose number of service requests does not exceed the capacity, the actual route is derived from that designed a priori by skipping customers with no demand. When the requests for service allocated to a plant exceed its capacity, a subset of them is randomly chosen to be served, and they are visited in the order defined by the a priori route.Penalties are paid for the unattended service requests. The expected total cost of the actual routes and the expected penalties for unserviced customers are contained in the recourse function.We present a two phase heuristic to solve this problem. In the first phase, a series of subproblems are sequentially solved to build an initial solution. In the second phase, this solution is successively improved using LS. This improving phase requires a high number of evaluations of the recourse function. Although we have developed an analytical expression for this recourse function, the computational effort required for its evaluation is considerable due to its combinatorial nature. For this reason, we approximate it with a simpler auxiliary function that has allowed us to obtain solutions in small computational times.We also propose a lower bound obtained from bounding different parts of the objective function independently. Unfortunately, we only could find reasonable bounds for the sum of fixed costs for opening the plants plus the expected penalty paid for unserviced customers. Further research is intended to improve the bounding of the expected total cost of the routes.The evaluation of the quality of the solutions obtained with our heuristic is not easy due to the lack of a tight global lower bound. However, the partial bound on the costs relative to the plants allows to conclude that the heuristic makes in general a good choice of the set of plants. As for the allocation of customers to plants and the design of the routes we can only evaluate the evolution along the search. In the computational experiences reported it can be seen that this evolution is satisfactory.

L’objet de notre projet de recherche est le développement d’un modèle de conception d’un réseau de distribution composé de trois niveaux : les usines, les centres de distribution (CD) et les clients. Nous supposons que le nombre et la localisation des usines ainsi que le nombre et la localisation des clients sont connus. Etant donné la demande des clients et une liste de CD potentiels, l’objectif est de déterminer la localisation des CD à ouvrir et d’y affecter les clients de manière à minimiser le coût total. En termes de modélisation, nous considérons divers aspects opérationnels qui sont inspirés d’une étude de cas dans l’industrie automobile. Ces aspect ont été pris en compte séparément dans la littérature mais jamais combinés dans un même modèle. Plus particulièrement, nous introduisons un « clustering » en prétraitement afin de modéliser les tournées de camions. Nous intégrons également des contraintes de volume minimum sur les axes de transport, des contraintes de volume minimum et de capacité maximale sur les centres de distribution, des contraintes de distance de couverture maximale et des contraintes d’uni-affectation. Par ailleurs, nous étudions une extension multi-périodes du problème en utilisant un « clustering » dynamique pour modéliser des tournées de camions multi-périodes. En termes de résolution, comme le problème étudié est NP-difficile au sens fort, nous proposons différentes méthodes heuristiques performantes basées sur la relaxation linéaire. A travers les tests effectués, nous montrons que ces méthodes fournissent des solutions proches de l’optimale en moins de temps de calcul que l’application directe d’un solveur linéaire. Nous analysons également la structure des réseaux de distribution obtenus et nous comparons les résultats issus de plusieurs versions du modèle afin de montrer la valeur ajoutée du « clustering » ainsi que de l’approche multi-périodes. / The purpose of our research project is to develop a distribution network design model taking into account many realistic features arising from a case-study in the field of car distribution. The overall network structure consists of three levels: plants, distribution centres (DCs) and customers. We assume that the number and location of the plants as well as the number and location of the customers are fixed. Given the demand of customers and a list of potential DCs, our main concern is to locate DCs and to assign customers to them in such a way as to minimize the total distribution costs. In terms of problem modeling, we integrate various operational features that were considered separately in the literature but have never been combined in a same model. Namely, we introduce a clustering-based approach to model vehicle routing, minimum volume constraints to ensure full truckload transport, minimum and maximum throughput constraints on DCs, maximum covering distance constraints and single sourcing restrictions. Furthermore, we study a multi-period extension of the problem using an original dynamic clustering to model multi-period vehicle routing. In terms of solution method, as the problem we study is NP-hard in the strong sense, we propose efficient heuristic procedures based on various types of linear relaxation. Through our numerical experiments, we show that the implemented heuristics offer near-optimal solutions with less computational effort than applying an exact MIP solver. We also analyze the structure of the obtained networks and compare the results of several versions of the model, highlighting the value of integrating a pre-processing clustering step and of using a multi-period approach.

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.