19 results on '"Ropke, Stefan"'
Search Results
2. Exact and Heuristic Methods for the Split Delivery Vehicle Routing Problem.
- Author
-
Gamst, Mette, Lusby, Richard Martin, and Ropke, Stefan
- Abstract
This paper describes an exact branch-and-cut (B&C) algorithm for the split delivery vehicle routing problem. The underlying model is based on a previously proposed two-index vehicle flow formulation that models a relaxation of the problem. We dynamically separate two well-known classes of valid inequalities, namely capacity and connectivity cuts, and use an in-out algorithm to improve the convergence of the cutting phase. We generate no-good cuts from feasible integer solutions to the relaxation using a recently proposed single-commodity flow formulation in the literature. The exact methodology is complemented by a very effective adaptive large neighborhood search (ALNS) heuristic that provides high-quality upper bounds to initiate the B&C algorithm. Key ingredients in the design of the heuristic include the use of a tailored construction algorithm, which can exploit the situation in which the ratio of the number of customers to the minimum number of vehicles needed is low, and the use of a route-based formulation to improve the solutions found before, during, and after the ALNS procedure. An earlier version of this work was submitted to the DIMACS (Center for Discrete Mathematics and Theoretical Computer Science) implementation challenge, where it placed third. On sets of well-known benchmark instances for limited and unlimited fleet variants of the problem, we demonstrate that the heuristic provides very competitive solutions, with respective average gaps of 0.19% and 0.18% from best-known values. Furthermore, the exact B&C framework is also highly competitive with state-of-the-art methods, providing solutions with an average optimality gap of 1.82%. History: This paper has been accepted for the Transportation Science Special Section on DIMACS Implementation Challenge: Vehicle Routing Problems. Supplemental Material: The online appendices are available at https://doi.org/10.1287/trsc.2022.0353. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
3. Cover Inequalities for a Vehicle Routing Problem with Time Windows and Shifts.
- Author
-
Dabia, Said, Ropke, Stefan, and van Woensel, Tom
- Subjects
- *
BACKPACKS , *MATHEMATICAL equivalence - Abstract
This paper introduces the vehicle routing problem with time windows and shifts (VRPTWS). At the depot, several shifts with nonoverlapping operating periods are available to load the planned trucks. Each shift has a limited loading capacity. We solve the VRPTWS exactly by a branch-and-cut-and-price algorithm. The master problem is a set partitioning with an additional constraint for every shift. Each constraint requires the total quantity loaded in a shift to be less than its loading capacity. For every shift, a pricing subproblem is solved by a label-setting algorithm. Shift capacity constraints define knapsack inequalities; hence we use valid inequalities inspired from knapsack inequalities to strengthen the linear programming relaxation of the master problem when solved by column generation. In particular, we use a family of tailored robust cover inequalities and a family of new nonrobust cover inequalities. Numerical results show that nonrobust cover inequalities significantly improve the algorithm. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
4. Simultaneous Optimization of Container Ship Sailing Speed and Container Routing with Transit Time Restrictions.
- Author
-
Karsten, Christian Vad, Ropke, Stefan, and Pisinger, David
- Subjects
- *
CONTAINER ships , *MARITIME shipping , *SCHEDULING , *TRANSSHIPMENT , *SPEED - Abstract
We introduce a decision support tool for liner shipping companies to optimally determine the sailing speed and needed fleet for a global network. We incorporate cargo routing decisions with tight transit time restrictions on each container such that we get a realistic picture of the utilization of the network. Furthermore, we show that it is possible to extend the model to include optimal time scheduling decisions such that the time associated with transshipments is also reflected accurately. To solve the speed optimization problem, we propose an exact algorithm based on Benders decomposition and column generation that exploits the separability of the problem. Computational results show that the method is applicable to liner shipping networks of realistic size and that it is important to incorporate cargo routing decisions when optimizing speed. The online appendix is available at https://doi.org/10.1287/trsc.2018.0818. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
5. The liquefied natural gas infrastructure and tanker fleet sizing problem.
- Author
-
Koza, David Franz, Ropke, Stefan, and Boleda Molas, Anna
- Subjects
- *
LIQUEFIED natural gas , *LIQUEFIED gas carriers , *TANKERS , *OPERATING costs , *COST effectiveness - Abstract
We consider a strategic infrastructure and tanker fleet sizing problem in the liquefied natural gas business. The goal is to minimize long-term on-shore infrastructure and tanker investment cost combined with interrelated expected cost for operating the tanker fleet. A non-linear arc-based model and an exact solution method based on a set-partitioning formulation are developed. The latter approach allows very fast solution times. Computational results for a case study with a liner shipping company are presented, including an extensive sensitivity analysis to account for limited predictability of key parameter values, to analyze the solutions’ robustness and to derive basic decision rules. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
6. Branch and Price for the Time-Dependent Vehicle Routing Problem with Time Windows.
- Author
-
Dabia, Said, Ropke, Stefan, van Woensel, Tom, and De Kok, Ton
- Subjects
- *
VEHICLE routing problem , *TRAVEL time (Traffic engineering) , *METAHEURISTIC algorithms , *ALGORITHMS , *COMBINATORIAL optimization - Abstract
This paper presents a branch-and-price algorithm for the time-dependent vehicle routing problem with time windows (TDVRPTW).We capture road congestion by considering time-dependent travel times, i.e., depending on the departure time to a customer, a different travel time is incurred. We consider the variant of the TDVRPTW where the objective is to minimize total route duration and denote this variant the duration minimizing TDVRPTW (DM-TDVRPTW). Because of time dependency, vehicles' dispatch times at the depot are crucial as road congestion might be avoided. Because of its complexity, all known solution methods to the DM-TDVRPTW are based on (meta-)heuristics. The decomposition of an arc-based formulation leads to a set-partitioning problem as the master problem, and a time-dependent shortest path problem with resource constraints as the pricing problem. The master problem is solved by means of column generation, and a tailored labeling algorithm is used to solve the pricing problem. We introduce new dominance criteria that allow more label dominance. For our numerical results, we modified Solomon's data sets by adding time dependency. Our algorithm is able to solve about 63% of the instances with 25 customers, 38% of the instances with 50 customers, and 15% of the instances with 100 customers. [ABSTRACT FROM AUTHOR]
- Published
- 2013
- Full Text
- View/download PDF
7. The traveling salesman problem with pickup and delivery: polyhedral results and a branch-and-cut algorithm.
- Author
-
Dumitrescu, Irina, Ropke, Stefan, Cordeau, Jean-François, and Laporte, Gilbert
- Subjects
- *
GRAPH theory , *POLYHEDRAL functions , *LINEAR programming , *MATHEMATICAL inequalities , *HAMILTONIAN systems , *ALGORITHMS - Abstract
The Traveling Salesman Problem with Pickup and Delivery (TSPPD) is defined on a graph containing pickup and delivery vertices between which there exists a one-to-one relationship. The problem consists of determining a minimum cost tour such that each pickup vertex is visited before its corresponding delivery vertex. In this paper, the TSPPD is modeled as an integer linear program and its polyhedral structure is analyzed. In particular, the dimension of the TSPPD polytope is determined and several valid inequalities, some of which are facet defining, are introduced. Separation procedures and a branch-and-cut algorithm are developed. Computational results show that the algorithm is capable of solving to optimality instances involving up to 35 pickup and delivery requests, thus more than doubling the previous record of 15. [ABSTRACT FROM AUTHOR]
- Published
- 2010
- Full Text
- View/download PDF
8. Branch and Cut and Price for the Pickup and Delivery Problem with Time Windows.
- Author
-
Ropke, Stefan and Cordeau, Jean-François
- Subjects
- *
BRANCH & bound algorithms , *LINEAR programming , *ADVANCED planning & scheduling , *ALGORITHMS , *NETWORK analysis (Planning) , *MATHEMATICAL programming - Abstract
In the pickup and delivery problem with time windows vehicle routes must be designed to satisfy a set of transportation requests, each involving a pickup and delivery location, under capacity, time window, and precedence constraints. This paper introduces a new branch-and-cut-and-price algorithm in which lower bounds are computed by solving through column generation the linear programming relaxation of a set partitioning formulation. Two pricing subproblems are considered in the column generation algorithm: an elementary and nonelementary shortest path problem. Valid inequalities are added dynamically to strengthen the relaxations. Some of the previously proposed inequalities for the pickup and delivery problem with time windows are also shown to be implied by the set partitioning formulation. Computational experiments indicate that the proposed algorithm outperforms a recent branch-and-cut algorithm. [ABSTRACT FROM AUTHOR]
- Published
- 2009
- Full Text
- View/download PDF
9. The Multiport Berth Allocation Problem with Speed Optimization: Exact Methods and a Cooperative Game Analysis.
- Author
-
Martin-Iradi, Bernardo, Pacino, Dario, and Ropke, Stefan
- Subjects
- *
CONTAINER terminals , *COOPERATIVE game theory , *MARITIME shipping , *REPRESENTATIONS of graphs , *SPEED - Abstract
We consider a variant of the berth allocation problem—that is, the multiport berth allocation problem—aimed at assigning berthing times and positions to vessels in container terminals. This variant involves optimizing vessel travel speeds between multiple ports, thereby exploiting the potentials of a collaboration between carriers (shipping lines) and terminal operators. Using a graph representation of the problem, we reformulate an existing mixed-integer problem into a generalized set partitioning problem, in which each variable refers to a sequence of feasible berths in the ports that the vessel visits. By integrating column generation and cut separation in a branch-and-cut-and-price procedure, our proposed method is able to outperform commercial solvers in a set of benchmark instances and adapt better to larger instances. In addition, we apply cooperative game theory methods to efficiently distribute the savings resulting from a potential collaboration and show that both carriers and terminal operators would benefit from collaborating. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
10. Integrated Liner Shipping Network Design and Scheduling.
- Author
-
Koza, David F., Desaulniers, Guy, and Ropke, Stefan
- Subjects
- *
SHIPPING containers , *NAVAL architecture , *CONTAINERIZATION , *TRANSSHIPMENT , *LINEAR programming , *FREIGHT & freightage - Abstract
In global liner shipping networks, a large share of transported cargo is transshipped at least once between container vessels, and the total transportation time of these containers depends on how well the corresponding services are synchronized. We propose a problem formulation that integrates service scheduling into the liner shipping network design problem. Furthermore, the model incorporates many industry-relevant modeling aspects: it allows for leg-based sailing speed optimization, it is not limited to simple or butterfly-type services, and it accounts for service-level requirements such as cargo transit time limits. The classic liner shipping network design problem is already a hard problem, and to solve the extended version, we propose a column-generation matheuristic that uses advanced linear programming techniques. The proposed method solves LINER-LIB instances of up to 114 ports and, if applied to the classic liner shipping network design problem, finds new best solutions to all instances, outperforming existing methods reported in the literature. Additionally, we analyze the relevance of scheduling for liner shipping network design. The results indicate that neglecting scheduling and approximating transshipments instead may result in the design of liner shipping networks that underestimate cargo transit times and their implications. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
11. An adaptive large neighborhood search metaheuristic for the vehicle routing problem with drones.
- Author
-
Sacramento, David, Pisinger, David, and Ropke, Stefan
- Subjects
- *
VEHICLE routing problem , *DRONE aircraft delivery , *TRAVELING salesman problem , *METAHEURISTIC algorithms , *NEIGHBORHOODS ,TRUCK fuel consumption - Abstract
Highlights • New optimization problem for delivery activities using drones in collaboration with trucks. • Fleet of delivery trucks, each of them equipped with a single drone. • Focus on cost-minimization objective function with maximum duration time for all routes. • Noteworthy cost-savings with respect to the case of only using trucks. • Efficient metaheuristic is proposed to solve this problem. Abstract Unmanned Aerial Vehicles, commonly known as drones, have attained considerable interest in recent years due to the potential of revolutionizing transport and logistics. Amazon were among the first to introduce the idea of using drones to deliver goods, followed by several other distribution companies working on similar services. The Traveling Salesman Problem , frequently used for planning last-mile delivery operations, can easily be modified to incorporate drones, resulting in a routing problem involving both the truck and aircraft. Introduced by Murray and Chu (2015) , the Flying Sidekick Traveling Salesman Problem considers a drone and truck collaborating. The drone can be launched and recovered at certain visits on the truck route, making it possible for both vehicles to deliver goods to customers in parallel. This generalization considerably decreases the operational cost of the routes, by reducing the total fuel consumption for the truck, as customers on the routes can be serviced by drones without covering additional miles for the trucks, and hence increase productivity. In this paper a mathematical model is formulated, defining a problem similar to the Flying Sidekick Traveling Salesman Problem , but for the capacitated multiple-truck case with time limit constraints and minimizing cost as objective function. The corresponding problem is denoted the Vehicle Routing Problem with Drones. Due to the difficulty of solving large instances to optimality, an Adaptive Large Neighborhood Search metaheuristic is proposed. Finally, extensive computational experiments are carried out. The tests investigate, among other things, how beneficial the inclusion of the drone-delivery option is compared to delivering all items using exclusively trucks. Moreover, a detailed sensitivity analysis is performed on several drone-parameters of interest. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
12. Improved formulations and an Adaptive Large Neighborhood Search heuristic for the integrated berth allocation and quay crane assignment problem.
- Author
-
Iris, Çağatay, Pacino, Dario, and Ropke, Stefan
- Subjects
- *
CONTAINER terminals , *HEURISTIC algorithms , *MARGINAL productivity , *DEVIATION (Statistics) , *FREIGHT & freightage - Abstract
This paper focuses on the integrated berth allocation and quay crane assignment problem in container terminals. We consider the decrease in the marginal productivity of quay cranes and the increase in handling time due to deviation from the desired position. We consider a continuous berth, discretized in small equal-sized sections. A number of enhancements over the state-of-the-art formulation and an Adaptive Large Neighborhood Search (ALNS) heuristic are presented. Computational results reveal that the enhancements improve many of the best-known bounds, and the ALNS outperforms the state-of-the-art heuristics for many instances. We also conduct further analysis on a new larger benchmark. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
13. Integrated Berth Allocation and Quay Crane Assignment Problem: Set partitioning models and computational results.
- Author
-
Iris, Çağatay, Pacino, Dario, Ropke, Stefan, and Larsen, Allan
- Subjects
- *
CONTAINER terminals , *INTEGER programming , *SET theory , *ECONOMIC impact , *RESOURCE allocation - Abstract
Most of the operational problems in container terminals are strongly interconnected. In this paper, we study the integrated Berth Allocation and Quay Crane Assignment Problem in seaport container terminals. We will extend the current state-of-the-art by proposing novel set partitioning models. To improve the performance of the set partitioning formulations, a number of variable reduction techniques are proposed. Furthermore, we analyze the effects of different discretization schemes and the impact of using a time-variant/invariant quay crane allocation policy. Computational experiments show that the proposed models significantly improve the benchmark solutions of the current state-of-art optimal approaches. [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
14. A note on a model for quay crane scheduling with non-crossing constraints.
- Author
-
Santini, Alberto, Friberg, Henrik Alsing, and Ropke, Stefan
- Subjects
- *
MATHEMATICAL models , *CONSTRAINT satisfaction , *COMPUTER scheduling , *COMPUTATIONAL complexity , *INTEGER programming - Abstract
This article studies the quay crane scheduling problem with non-crossing constraints, which is an operational problem that arises in container terminals. An enhancement to a mixed integer programming model for the problem is proposed and a new class of valid inequalities is introduced. Computational results show the effectiveness of these enhancements in solving the problem to optimality. [ABSTRACT FROM PUBLISHER]
- Published
- 2015
- Full Text
- View/download PDF
15. The time constrained multi-commodity network flow problem and its application to liner shipping network design.
- Author
-
Karsten, Christian Vad, Pisinger, David, Ropke, Stefan, and Brouer, Berit Dangaard
- Subjects
- *
PROBLEM solving , *MARITIME shipping , *HEURISTIC algorithms , *COMMERCIAL products , *SHIPMENT of goods - Abstract
The multi-commodity network flow problem is an important sub-problem in several heuristics and exact methods for designing route networks for container ships. The sub-problem decides how cargoes should be transported through the network provided by shipping routes. This paper studies the multi-commodity network flow problem with transit time constraints which puts limits on the duration of the transit of the commodities through the network. It is shown that for the particular application it does not increase the solution time to include the transit time constraints and that including the transit time is essential to offer customers a competitive product. [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
16. A Branch-and-Cut Algorithm for the Symmetric Two-Echelon Capacitated Vehicle Routing Problem.
- Author
-
Jepsen, Mads, Spoorendonk, Simon, and Ropke, Stefan
- Subjects
- *
VEHICLE routing problem , *TRANSPORTATION problems (Programming) , *ALGORITHMS , *COMBINATORIAL optimization , *ECHELON (Surveillance system) - Abstract
This paper presents an exact method for solving the symmetric two-echelon capacitated vehicle routing problem, a transportation problem concerned with the distribution of goods from a depot to a set of customers through a set of satellite locations. The presented method is based on an edge flow model that is a relaxation and provides a valid lower bound. A specialized branching scheme is employed to obtain feasible solutions. Out of a test set of 93 instances the algorithm is able to solve 47 to optimality, surpassing previous exact algorithms. [ABSTRACT FROM AUTHOR]
- Published
- 2013
- Full Text
- View/download PDF
17. Models for the discrete berth allocation problem: A computational comparison
- Author
-
Buhrkal, Katja, Zuglian, Sara, Ropke, Stefan, Larsen, Jesper, and Lusby, Richard
- Subjects
- *
CONTAINER terminals , *RESERVATION systems , *INTEGER programming , *NUMERICAL analysis , *COMMUNICATIONS industries , *MATHEMATICAL models , *COMPARATIVE studies , *PROBLEM solving - Abstract
Abstract: In this paper we consider the problem of allocating arriving ships to discrete berth locations at container terminals. This problem is recognized as one of the most important processes for any container terminal. We review and describe three main models of the discrete dynamic berth allocation problem, improve the performance of one model, and, through extensive numerical tests, compare all models from a computational perspective. The results indicate that a generalized set-partitioning model outperforms all other existing models. [Copyright &y& Elsevier]
- Published
- 2011
- Full Text
- View/download PDF
18. Flexible ship loading problem with transfer vehicle assignment and scheduling.
- Author
-
Iris, Çağatay, Christensen, Jonas, Pacino, Dario, and Ropke, Stefan
- Subjects
- *
SHIP loading & unloading , *TRANSPORT vehicles , *SHIPPING containers , *CONTAINER terminals , *HEURISTIC algorithms , *PRODUCTION scheduling - Abstract
This paper presents the flexible containership loading problem for seaport container terminals. The integrated management of loading operations, planning of the transport vehicles to use and their scheduling is what we define as the Flexible Ship Loading Problem (FSLP). The flexibility comes from a cooperative agreement between the terminal operator and the liner shipping company, specifying that the terminal has the right to decide which specific container to load for each slot obeying the class-based stowage plan received from the liner. We formulate a mathematical model for the problem. Then we present various modelling enhancements and a mathematical model to obtain strong lower bounds. We also propose a heuristic algorithm to solve the problem. It is shown that enhancements improve the performance of formulation significantly, and the heuristic efficiently generates high-quality solutions. Results also point out that substantial cost savings can be achieved by integrating the ship loading operations. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
19. The Simultaneous Vehicle Scheduling and Passenger Service Problem.
- Author
-
Petersen, Hanne L., Larsen, Allan, Madsen, Oli B. G., Petersen, Bjørn, and Ropke, Stefan
- Subjects
- *
TRANSPORTATION research , *PUBLIC transit , *TRANSPORTATION planning , *OPERATING costs , *TRANSPORTATION schedules , *INTEGER programming , *METAHEURISTIC algorithms - Abstract
Passengers using public transport systems often experience waiting times when transferring between two scheduled services. In this paper we propose a planning approach that seeks to obtain a favourable trade-off between the two contrasting objectives, passenger service and operating cost, by modifying the timetable. The planning approach is referred to as the simultaneous vehicle scheduling and passenger service problem (SVSPSP). The SVSPSP is modelled as an integer programming problem and solved using a large neighborhood search metaheuristic. The proposed framework is tested on data inspired by the express-bus network in the Greater Copenhagen area. The results are encouraging and indicate a potential decrease of passenger transfer waiting times in the network of up to 20%, with the vehicle scheduling costs remaining mostly unaffected. [ABSTRACT FROM AUTHOR]
- Published
- 2013
- Full Text
- View/download PDF
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.