Search

With the new distribution demands emerging continuously in the last decade, the distribution mode is changing gradually in various applications, such as e-commerce, emergency relief supplies distribution, the last-mile delivery, and so on. We formulate vehicle routing problem with pickup and delivery (VRPPD), while simultaneously considering multiple arrival time and traffic congestion constraints. Our model focuses on the clear changes of the distribution mode to meet the fast-delivery requirements in the last decade, which is characterized by the multi-batch arrival of goods in 24 hours and time-varying congestion in various time windows. Besides, we propose dynamic memory memetic algorithm, which updates its dynamic memory by whether to promote populations to find new better solutions or not. This is an effective acceleration mechanism to promote the population progress. Meanwhile, dynamic memory memetic algorithm determines the serious congestion tasks in the delivery route and transforms them into normal congestion or even non-congestion tasks. Test sets with 30 test problems are constructed by using real distribution data from Alibaba Cloud and traffic congestion data from Baidu Map in Shanghai. By comparing with four compared algorithms, the effectiveness, efficiency, and robustness of our proposed algorithm in non-congestion and congestion tests are simultaneously demonstrated.

The pickup and delivery problem with time windows (PDPTW) is studied in this paper. It is referred to as the single-commodity capacitated vehicle routing problem with pickups and deliveries, in which a fleet of vehicles meet a group of customer demands. Each customer demand includes the usage of only one vehicle for both loading a specified quantity of one type of commodity at one place and delivering them to another place. All the demands of customers must be satisfied without exceeding the vehicle capacity and the pickup or delivery places time windows specified for each place. In this study, we introduce a novel Constraint Programming (CP) model for the PDPTW. CP is an exact solution approach that is popular for its performance to state complicated relationships and to achieve high-quality solutions within acceptable computational times for combinatorial optimization problems with complicated constraints such as the PDPTW. The performance of the proposed CP model is tested with well-known benchmark instances from literature. The results of computational analysis indicate that our CP model is very effective in finding high-quality solutions for even large size problems.

International audience; The Pickup and Delivery Problem (PDP) consists in defining a set of routes that satisfy transportation requests between a set of pickup points and a set of delivery points. This paper addresses a variant of the PDP where requests can change vehicle during their trip. The transshipment is made at specific locations called "transfer points". The corresponding problem is called the Pickup and Delivery with Transfers (PDPT). Solving the PDPT leads to new modeling and algorithmic difficulties. We propose new heuristics capable of efficiently inserting requests through transfer points. These heuristics are embedded into an Adaptive Large Neighborhood Search. We evaluate the method on generated instances and apply it to the transportation of people with disabilities. On these real-life instances we show that the introduction of transfer points generally brings non-negligible improvements (up to 9%). Experiments on related instances from the literature show clearly that the method is competitive with existing method.

In this paper, we study a rich vehicle routing problem incorporating various complexities found in real-life applications. The General Vehicle Routing Problem (GVRP) is a combined load acceptance and generalised vehicle routing problem. Among the real-life requirements are time window restrictions, a heterogeneous vehicle fleet with different travel times, travel costs and capacity, multi-dimensional capacity constraints, order/vehicle compatibility constraints, orders with multiple pickup, delivery and service locations, different start and end locations for vehicles, and route restrictions for vehicles. The GVRP is highly constrained and the search space is likely to contain many solutions such that it is impossible to go from one solution to another using a single neighbourhood structure. Therefore, we propose iterative improvement approaches based on the idea of changing the neighbourhood structure during the search.

The Pickup and Delivery Problem with Transfers (PDPT) consists of defining a set of minimum cost routes in order to satisfy a set of transportation requests, allowing them to change vehicles at specific locations. In this problem, routes are strongly interdependent due to request transfers. Then it is critical to efficiently check if inserting a request into a partial solution is feasible or not. In this article, we present a method to perform this check in constant time.

Due to the growing dynamics and complexity of logistic systems, common concepts of planning and control are being pushed to their limits. In addition to that, structural changes in technology are driving new functionality into logistic systems. These circumstances require changes of processes, planning and control in this field. The new concept of autonomous control applies an object-oriented point of view. The core is the self-contained decision and routing of logistic objects within changing environments. The presented work gives a framework protocol, based on algorithms from data communication, as a general concept for autonomous routing adaptive to many fields. This framework protocol was named Distributed Logistics Routing Protocol (DLRP). The DLRP is adapted to transport and to production logistics where it is being compared to common algorithms (for VRP, PDP and FFP). This shows a comparable performance and a high potential of the DLRP to improve logistic processes.

Transportation companies face gradually larger problems where the use of transshipment can have a significant outcome on the costs. ILOG TPO is a software able to solve such problems, but it is hard for it to take good cross-docking decisions. Moreover, the ILOG TPO solving process is based on local search, and it can be helped for global decisions such as transshipment. This PhD takes place in this context, and its aim is to help ILOG TPO find better solutions. For this matter, a complete formulation is first proposed to solve the smallest instances, and with a cutting-plane technique, optimal solutions are usually found within reasonnable computing time. Then a two-phase algorithm including a network Mixed-Integer Program (MIP) on a network relaxation of the problem is given for larger instances. This two-phase algorithm is a cooperation between the MIP and ILOG TPO, where the MIP gives ILOG TPO, for each shipment, the hub path through which it should be routed. This heuristic finds similar solutions as ILOG TPO alone, but the processing time is significantly reduced.; Les entreprises de transport font face à des problèmes de taille grandissante où l'utilisation de transbordement peut avoir un impact significatif sur les coûts. ILOG TPO est un logiciel capable de résoudre de tels problèmes, mais il lui est difficile de prendre de bonnes décisions concernant le transbordement. De plus, le processus de résolution d'ILOG TPO est basé sur la recherche locale, et il peut être aidé pour certaines décisions globales comme le transbordement. Cette thèse se place dans ce contexte, et son objectif est d'aider ILOG TPO à trouver de meilleures solutions. Pour cela, une formulation complète est d'abord proposée pour résoudre les plus petites instances, et avec une technique de plans coupants, les solutions optimales sont généralement trouvées en un temps raisonnable. Ensuite, un algorithme à deux phases qui inclut un programme en variables mixtes (MIP) sur une relaxation de type réseau du problème est donné pour de plus grandes instances. Cet algorithme est une coopération entre le MIP et ILOG TPO, où le MIP donne à ILOG TPO, pour chaque ordre de transport, le chemin de hubs par lequel il devrait être acheminé. Cette heuristique trouve des solutions similaires à ILOG TPO seul, mais le temps de calcul est réduit de façon significative.

Transportation companies face gradually larger problems where the use of transshipment can have a significant outcome on the costs. ILOG TPO is a software able to solve such problems, but it is hard for it to take good cross-docking decisions. Moreover, the ILOG TPO solving process is based on local search, and it can be helped for global decisions such as transshipment. This PhD takes place in this context, and its aim is to help ILOG TPO find better solutions. For this matter, a complete formulation is first proposed to solve the smallest instances, and with a cutting-plane technique, optimal solutions are usually found within reasonnable computing time. Then a two-phase algorithm including a network Mixed-Integer Program (MIP) on a network relaxation of the problem is given for larger instances. This two-phase algorithm is a cooperation between the MIP and ILOG TPO, where the MIP gives ILOG TPO, for each shipment, the hub path through which it should be routed. This heuristic finds similar solutions as ILOG TPO alone, but the processing time is significantly reduced., Les entreprises de transport font face à des problèmes de taille grandissante où l'utilisation de transbordement peut avoir un impact significatif sur les coûts. ILOG TPO est un logiciel capable de résoudre de tels problèmes, mais il lui est difficile de prendre de bonnes décisions concernant le transbordement. De plus, le processus de résolution d'ILOG TPO est basé sur la recherche locale, et il peut être aidé pour certaines décisions globales comme le transbordement. Cette thèse se place dans ce contexte, et son objectif est d'aider ILOG TPO à trouver de meilleures solutions. Pour cela, une formulation complète est d'abord proposée pour résoudre les plus petites instances, et avec une technique de plans coupants, les solutions optimales sont généralement trouvées en un temps raisonnable. Ensuite, un algorithme à deux phases qui inclut un programme en variables mixtes (MIP) sur une relaxation de type réseau du problème est donné pour de plus grandes instances. Cet algorithme est une coopération entre le MIP et ILOG TPO, où le MIP donne à ILOG TPO, pour chaque ordre de transport, le chemin de hubs par lequel il devrait être acheminé. Cette heuristique trouve des solutions similaires à ILOG TPO seul, mais le temps de calcul est réduit de façon significative.