139 research outputs found
A mathematical model for the Multi-Levels Product Allocation Problem in a warehouse with compatibility constraints
No full textThe aim of this work is to address the products allocation problem in a multi-layers warehouse with compatibility constraints among the classes. The problem under study represents one of the most relevant topic in Logistics. The goal is to reduce, as much as possible, the delivery times; the inventories; the total logistic costs and to guarantee, at the same time, higher service levels (i.e., high customers satisfaction degree). In this work, a linear model to mathematically represent the problem is developed and its performance is evaluated on a set of instances, representing realistic situations. A sensitivity analysis is
also carried out by considering the most relevant parameters of the model. Finally, an Iterated Local Search based heuristic is defined in order to solve large scale scenarios in a reasonable amount of time. Numerical results show that the proposed heuristic is able to find
good quality solutions with a computational effort lower than that required to solve the proposed mathematical model
A New Constructive Heuristic for the Undirected Rural Postman Problem
No full textThis paper describes a constructive heuristic for the well-known Undirected Rural Postman Problem. At each iteration, the procedure inserts a connected component of the required edges and performs a local postoptimization. Computational results on a set of benchmark instances with up to 350 vertices show that the proposed procedure is competitive with the classical Frederickson procedure. Its use is recommended when a high-quality solution is needed in a short amount of time (e.g., in laser plotter applications)
Solving Stochastic Linear Programs with Restricted Recourse using Interior Point Methods
No full textAn exact approach for the capacitated vehicle routing problem with twodimensional loading constraints
No full textThe classical Capacitated Vehicle Routing Problem [2] calls for the determination of the optimal set of routes to be performed by a fleet of vehicles, each with a maximum transport capacity, in order to satisfy the demands of a given set of customers. The demands are usually expressed by a positive integer, representing the weight or volume to be delivered.
This can lead to a too strong approximation for many practical routing applications, where real demands are composed by items of a given size, and the loading of these items into the vehicles can be difficult. We consider the practical case in which the demand of each
customer is defined by a set of rectangular items, each with a given weight and base dimensions. Thus, loading these items into a vehicle requires both checking that the maximum weight capacity is respected, and that the two-dimensional loading is feasible.
The problem is composed by a routing part, which was solved through a branch and cut technique, and by a loading part, solved through a dedicated branch and bound derived from the one proposed in [1]. Separation procedures and lower bounds were developed for the new problem, as well as greedy heuristics and local search. The algorithm was coded in C and tested on instances derived from those available in the literature, being able to solve
to optimality instances with up to 35 customers and 110 items.
References:
[1] S. Martello and D. Vigo. Exact Solution of the Two-Dimensional Finite Bin Packing Problem.
Management Science 44, 388 - 399 (1998).
[2] The Vehicle Routing Problem. P. Toth and D. Vigo editors. SIAM Monographs on Discrete
Mathematics and Applications (2002)
- …
