1,721,004 research outputs found
The storage location assignment and picker routing problem: A generic branch-cut-and-price algorithm
Full text linkThe Storage Location Assignment Problem (SLAP) and the Picker Routing Problem (PRP) have received significant attention in the literature due to their pivotal role in the performance of the Order Picking (OP) activity, the most resource-intensive process of warehousing logistics. The two problems are traditionally considered at different decision-making levels: tactical for the SLAP, and operational for the PRP. However, this paradigm has been challenged by the emergence of modern practices in e-commerce warehouses, where decisions are more dynamic. This shift makes the integrated problem, called the Storage Location Assignment and Picker Routing Problem (SLAPRP), pertinent to consider. Scholars have investigated several variants of the SLAPRP, including different warehouse layouts and routing policies. Nevertheless, the available computational results suggest that each variant requires an ad-hoc formulation. Moreover, achieving a complete integration of the two problems, where the routing is solved optimally, remains out of reach for commercial solvers, even on trivial instances. In this paper, we propose an exact solution framework that addresses a broad class of variants of the SLAPRP, including all the previously existing ones. This paper proposes a Branch-Cut-and-Price framework based on a novel formulation with an exponential number of variables, which is strengthened with a novel family of non-robust valid inequalities. We have developed an ad-hoc branching scheme to break symmetries and maintain the size of the enumeration tree manageable. Computational experiments show that our framework can effectively solve medium-sized instances of several SLAPRP variants and outperforms the state-of-the-art methods from the literature
The Multi-Trip Vehicle Routing Problem with Time Windows and Release Dates
No full textThe multi-trip vehicle routing problem with time windows and release dates is a variant of the multi-trip vehicle routing problem where a time window and a release date are associated with each customer. The release date represents the date when the merchandise requested by a customer becomes available at the depot. The interest for this problem comes from the field of city logistics and the study of delivery systems involving City Distribution Centers (CDC). In these systems, goods are first delivered to a CDC before being transferred to eco-friendly vehicles for final delivery. We propose to address the problem through a population-based algorithm, with a giant tour representation for individuals. An efficient labeling procedure allows turning giant tours into solutions. Experiments demonstrate the effectiveness of the method
Vehicle routing problems with multiple trips
No full textThis paper presents a survey on the multi-trip vehicle routing problem (MTVRP) and on related routing problems where vehicles are allowed to perform multiple trips. The first part of the paper focuses on the MTVRP. It gives an unified view on mathematical formulations and surveys exact and heuristic approaches. The paper continues with variants of the MTVRP and other families of routing problems where multiple trips are sometimes allowed. For the latter, it specially insists on the motivations for having multiple trips and the algorithmic consequences. The expected contribution of the survey is to give a comprehensive overview on a structural property of routing problems that has seen a strongly growing interest in the last few years and that has been investigated in very different areas of the routing literature
A note on the complexity of the picker routing problem in multi-block warehouses and related problems
No full textThe Picker Routing Problem (PRP), which consists of finding a minimum-length tour between a set of storage locations in a warehouse, is one of the most important problems in the warehousing logistics literature. Despite its popularity, the tractability of the PRP in multi-block warehouses remains an open question. This technical note aims to fill this research gap by establishing that the problem is strongly NP-hard. As a corollary, the complexity status of other related problems is settled
A heuristic with a performance guarantee for the commodity constrained split delivery vehicle routing problem
No full textThe commodity constrained split delivery vehicle routing problem (C-SDVRP) is a routing problem where customer demands are composed of multiple commodities. A fleet of capacitated vehicles must serve customer demands in a way that minimizes the total routing costs. Vehicles can transport any set of commodities and customers are allowed to be visited multiple times. However, the demand for a single commodity must be delivered by one vehicle only. In this work, we developed a heuristic with a performance guarantee to solve the C-SDVRP. The proposed heuristic is based on a set covering formulation, where the exponentially-many variables correspond to routes. First, a subset of the variables is obtained by solving the linear relaxation of the formulation by means of a column generation approach which embeds a new pricing heuristic aimed to reduce the computational time. Solving the linear relaxation gives a valid lower bound used as a performance guarantee for the heuristic. Then, we devise a restricted master heuristic to provide good upper bounds: the formulation is restricted to the subset of variables found so far and solved as an integer program with a commercial solver. A local search based on a mathematical programming operator is applied to improve the solution. We test the heuristic algorithm on benchmark instances from the literature. The comparison with the state-of-the-art heuristics for solving the C-SDVRP shows that our approach significantly improves the solution time, while keeping a comparable solution quality and improving some best-known solutions. In addition, our approach is able to solve large instances with 100 customers and six commodities, and also provides very good quality lower bounds. Furthermore, an instance of the C-SDVRP can be transformed into a CVRP instance by simply duplicating each customer as many times as the requested commodities and by assigning as demand the demand of the single commodity. Hence, we compare heuristics for the C-SDVRP against the state-of-the-art heuristic for the Capacitated Vehicle Routing Problem (CVRP). The latter approach revealed to have the best performance. However, our approach provides solutions of comparable quality and has the interest of providing a performance guarantee
A column generation based heuristic for the generalized vehicle routing problem with time windows
Full text linkThe generalized vehicle routing problem with time windows (GVRPTW) is defined on a directed graph G=(V,A) where the vertex set V is partitioned into clusters. One cluster contains only the depot, where is located a homogeneous fleet of vehicles, each with a limited capacity. The other clusters represent customers. A demand is associated with each cluster. Inside a cluster, the vertices represent the possible locations of the customer. A time window is associated with each vertex, during which the visit must take place if the vertex is visited. The objective is to find a set of routes such that the total traveling cost is minimized, exactly one vertex per cluster is visited, and all the capacity and time constraints are respected. This paper presents a set covering formulation for the GVRPTW which is used to provide a column generation based heuristic to solve it. The proposed solving method combines several components including a construction heuristic, a route optimization procedure, local search operators and the generation of negative reduced cost routes. Experimental results on benchmark instances show that the proposed algorithm is efficient and high-quality solutions for instances with up to 120 clusters are obtained within short computation times
Two-echelon distribution with a single capacitated hub
No full textIn this paper, we investigate the synchronization between the two echelons in two-echelon urban distribution systems. The first echelon aims at transferring goods from a warehouse to a (single) city hub located in the city center. The second echelon, managed with a fleet of environmentally friendly vehicles, delivers goods to final customers, from the city hub. The two echelons are synchronized in time but also with regards to the capacity of the city hub. As far as we know, this is the first study considering the latter issue in the context of two-echelon distribution. To deal with the synchronization while optimizing the distribution, we propose a three-phase heuristic solution approach. At first, our approach optimizes the distribution for the second echelon. Then, it manages the synchronization. Finally, it optimizes the distribution for the first echelon. Population-based metaheuristics and integer programs are used. Results show the effectiveness of the method and permit to derive managerial insights on the distribution
Improving neighborhood exploration into MOEA/Dframework to solve a bi-objective routing problem
No full textA heuristic branch-cut-and-price algorithm for the ROADEF/EURO challenge on Inventory Routing
No full textThis paper is part of the special section devoted to the ROADEF/EURO challenge on inventory routing. We propose an extended formulation that we address with a heuristic branch-cut-and-price method. Among the difficulties that we had to face are a fractional objective function, the simultaneous generation of constraints and columns, and a complex pricing problem. We evaluate our approach on the benchmark instances proposed for the challenge
- …
