1,721,028 research outputs found
A column generation approach for the Multi-Vehicle Travelling Purchaser Problem with Pairwise Incompatibility Constraints
No full textA branch-and-price algorithm for the Multi-Vehicle Travelling Purchaser Problem with Pairwise Incompatibility Constraints and Unitary Demands
No full textVehicle Purchaser Problem with Exclusionary Side Constraints
No full textIn Vehicle Purchaser Problem (VPP) a fleet of vehicles is available to visit suppliers offering
different products at different prices and quantities. The VPP aims at selecting a subset of
suppliers so to satisfy products demand at the minimum traveling and purchasing costs, while
ensuring that the quantity collected by each vehicle does not exceed a predefined capacity (see
[1] for an application to school bus routing). We study a variant of the VPP characterized by
the addition of exclusionary side constraints representing the impossibility of loading incompatible
products on the same vehicle (e.g. food and chemicals). The problem finds application
in a City Logistics context, where a major issue concerns the products distribution in city
centers minimizing traffic congestion and air pollution (see [2]). In particular, the problem
models the practical situation where a depot is placed on border of a city center and collects,
from different suppliers, products addressed to customers located inside the city. Given the
variety of products requested, incompatibility constraints represent a relevant aspect of the
problem. We call this VPP variant Capacitated Vehicle Purchaser Problem with Exclusionary
Side Constraints (CVPP-ESC). The problem is strongly NP-hard and to the best of our
knowledge it has never been addressed in the literature. We propose both exact and heuristic
approaches to solve the problem. Some preliminary results are in progress.
References
(1) J. Riera-Ledesma, J.J. Salazar-Gonz ́alez, Solving school bus routing using the
multiple vehicle traveling purchaser problem: A branch-and-cut approach,
Computers & Operations Research 39:391–404 (2012).
(2) T.G. Crainic, N. Ricciardi, G. Storchi, Models for Evaluating and Planning City
Logistics Transportation Systems, Transportation Science 43:432-454 (2009)
A learning-based granular variable neighborhood search for a multi-period election logistics problem with time-dependent profits
Full text linkPlanning the election campaign for leaders of a political party is a complex problem. The party representatives, running mates, and campaign managers have to design an efficient routing and scheduling plan to visit multiple locations while respecting time and budget constraints. Given the limited time of election campaigns in most countries, every minute should be used effectively, and there is very little room for error. In this paper, we formalize this problem as the multiple Roaming Salesman Problem (mRSP), a new variant of the recently introduced Roaming Salesman Problem (RSP), where a predefined number of political representatives visit a set of cities during a planning horizon to maximize collected rewards, subject to budget and time constraints. Cities can be visited more than once and associated rewards are time-dependent (increasing over time) according to the day of the visit and the recency of previous visits. We develop a compact Mixed Integer Linear Programming (MILP) formulation complemented with effective valid inequalities. Since commercial solvers can obtain optimal solutions only for small-sized instances, we develop a Learning-based Granular Variable Neighborhood Search and demonstrate its capability of providing high-quality solutions in short CPU times on real-world instances. The adaptive nature of our algorithm refers to its ability to dynamically adjust the neighborhood structure based on the progress of the search. Our algorithm generates the best-known results for many instances
An effective hybrid heuristic for the Capacitated Total Quantity Discount Problem
No full textTechnical Report n. 2011-03-67, Department of Electronics for Automation, University of Bresci
Multi-Vehicle Traveling Purchaser Problem with Exclusionary Side Constraints
No full textRecently, an interesting variant of the Vehicle Routing Problem (VRP), where a fleet of vehicles is
available to visit suppliers offering different products at different prices and quantities, has been studied.
The problem, called Multi-Vehicle Travelling Purchaser Problem (MVTPP), aims at selecting a subset of
suppliers so to satisfy products demand at the minimum travelling and purchasing costs, while ensuring
that the quantity collected by each vehicle does not exceed a predefined capacity (see Riera-Ledesma and
Salazar-Gonzalez [1] for an application to school bus routing). More recently, Bianchessi et al. [2] study
the Distance-Constrained MVTPP where a constraint ensures that the distance travelled by each vehicle
does not exceed a predefined upper bound.
We introduce a generalization of the MVTPP characterized by the presence of exclusionary side
constraints representing the impossibility of loading products on the same vehicle when incompatible (e.g.
food and chemicals) and call it Multi-Vehicle Travelling Purchaser Problem with Exclusionary Side
Constraints (MVTPP-ESC). Exclusionary constraints have been slightly studied in the literature (see e.g.
Sun [3] where such constraints are added to the Transportation Problem) but, to the best of our
knowledge, the complete MVTPP-ESC has never been addressed before.
The problem typically finds application in distribution logistics, more specifically in a City Logistics
context where a major issue concerns the products distribution in city centers, while minimizing traffic
congestion and air pollution together with purchasing cost. In particular, the problem models the practical
situation where a depot is placed on border of a city center and collects, from different suppliers, products
addressed to customers located inside the city. Given the variety of products requested and the similarity
of the available vehicles, incompatibility constraints represent a relevant aspect of the problem.
We develop new classes of valid inequalities for the problem and propose a B&C algorithm. We also
introduce a heuristic procedure that exploits some structural properties of the problem. Preliminary results
on new benchmark instances seem to be very promising.
References
[1] J. Riera-Ledesma, J.J. Salazar-Gonzalez, Solving school bus routing using the multiple vehicle
traveling purchaser problem: A branch-and-cut approach, Computers and Operations Research 39 (2012)
391-404.
[2] N. Bianchessi, M.G. Speranza, R. Mansini, The Distance-Constrained Vehicle Purchaser Problem, In
proceedings of Odysseus 2012 - 5th International Workshop on Freight Transportation and Logistics
(2012).
[3] M. Sun, The transportation problem with exclusionary side constraints and two branch-and-bound
algorithms, European Journal of Operational Research 140 (2002) 629-647
An Effective Matheuristic for the Capacitated Total Quantity Discount Problem
No full textNew generation algorithms focus on hybrid miscellaneous of exact and heuristic methods. Combining meta-heuristics and exact methods based on mathematical models appears to be a very promising alternative in solving many combinatorial optimization problems.
In this paper we introduce a matheuristic method exploiting the optimal solution of mixed integer subproblems to solve the complex supplier selection problem of a company that needs to select a subset of suppliers so to minimize purchasing costs while satisfying products demand. Suppliers offer products at given prices and apply discounts according to the total quantity purchased. The problem, known as Total Quantity Discount Problem (TQDP), is strongly NP-hard thus motivating the study of effective and efficient heuristic methods. The proposed solution method is strengthened by the introduction of an Integer Linear Programming (ILP) refinement approach. An extensive computational analysis on a set of benchmark instances available in the literature has shown how the method is efficient and extremely effective allowing to improve existing best known solution values
Portfolio Optimization with Transaction Costs
No full textWhen buying and selling assets on the markets, the investors incur in payment of commissions and other costs, globally defined transaction costs, that are charged by the brokers or the financial institutions playing the role of intermediary. Transaction costs represent the most important feature to account for when selecting a real portfolio, since they diminish net returns and reduce the amount of capital available for future investments. In this chapter, we show that transaction costs may have different structures and that we need for a specific use of variables and constraints to express the transaction costs in linear form. We specify that a model may account for transaction costs in different ways. Transaction costs may be treated separately in a constraint imposing they should not exceed a predefined amount or be deducted from the expected portfolio return and/or diminish the capital available for the actual investment. When a complete portfolio optimization model is defined, some of the constraints on the definition of the transaction costs may be relaxed without affecting the correctness of the model as the optimization ’pushes’ the transaction costs to the minimum value allowed by the constraints. In this chapter, we first present the most common structures of transaction costs including fixed, proportional, with minimum charge, convex and concave piecewise linear costs, and see how to model them. We then discuss the different ways to account for transaction costs in a portfolio optimization model. Finally, we present, as an example, a complete portfolio optimization model using CVaR as objective function
- …
