Chair: Cláudio Alves, Universidade do Minho, Portugal
Optimization algorithms for the integrated vehicle routing and packing problem
Telmo Pinto (email@example.com), Cláudio Alves (firstname.lastname@example.org), José Valério de Carvalho (email@example.com)
Recently, some works have emphasized the integration of the capacitated vehicle routing problem (CRVP) with other optimization problems in order to approximate the resolution of these problems to real-world applications. One of these integrated problems considers not only the capacity of the vehicles as the way in which the items are loaded, and consequently the way the items are delivered to the customers. Some additional constraints may be considered, such as the orientation of the items or time windows for their delivery. This problem is described in the literature as the capacitated vehicle routing problem with loading constraints (L-CVRP), and it combines the generation of routes with two- or three-dimensional packing (2L-CVRP and 3L-CVRP, respectively). The difficulty in solving exactly the L-CVRP explains the fact that most of the contributions are based on heuristics. However, some recent works have addressed both the exact solution of the LVRP and the exact solution of two-dimensional packing problems explicitly considering loading constraints. In this presentation, we intend to describe new approaches towards the exact resolution of the 2L-CVRP based on column generation and integer programming based approaches.
Keywords: Vehicle routing, Packing, Integer Programming
Integer programming based approaches for multi-trip location routing
Rita Macedo (firstname.lastname@example.org), Cláudio Alves (email@example.com), Said Hanafi (Said.Hanafi@univ-valenciennes.fr), José Valério de Carvalho (firstname.lastname@example.org), Bruna Ramos (email@example.com), Nenad Mladenovic (Nenad.Mladenovic@univ-valenciennes.fr)
The multi-trip location routing problem consists in selecting the depots to open and the routes that should be performed to serve a set of clients at minimum cost. The multi-trip variant considers the possibility for a vehicle to perform more than a single route during the planning period, and hence it applies typically to cases in which the trips are realized within a small geographic area and involves for example the transportation of perishable goods. As a consequence, the inherent complexity of the problem increases as it has now to determine which routes should be assigned to the vehicles. In this paper, we explore an improved network flow formulation for this problem, and we compare it with another compact formulation proposed in the literature. We describe also an iterative rounding heuristic that relies on this model. We show through computational experiments on benchmark instances that the model provides good lower bounds, and that it can be used both by commercial solvers and heuristics to derive good quality solutions for the problem.
Keywords: Location, Multi-trip routing, Integer Programming
Exact solution of combined cutting stock and scheduling problems
Nuno Braga (firstname.lastname@example.org), Cláudio Alves (email@example.com), José Valério de Carvalho (firstname.lastname@example.org)
The combination of cutting and packing with scheduling has been addressed recently by different authors considering both one- and two-dimensional instances. These problems consist essentially in finding the cutting plan that minimizes a function of the wastage and tardiness related to the items delivery given a set of due dates (and possibly release dates). As shown by other authors, some of these models may not be exact due to the definition of the time periods on which they rely. In this paper, we explore an exact and compact assignment formulation for the combined cutting stock and scheduling. The model is general in the sense that it applies to instances with any level of demand per item. To strengthen the model, we resort to knapsack-based inequalities derived using dual-feasible functions. Up to now, these functions have been used mainly to derive lower bounds for cutting and packing problems. Different computational experiments performed on benchmark instances illustrate their potential as an effective cutting plane tool.
Keywords: Cutting and packing, Scheduling, Integer Programming