1,721,019 research outputs found
New Solution Approaches for the Capacitated Supplier Selection Problem with Total Quantity Discount and Activation Costs under Demand Uncertainty
No full textAn exact algorithm for the Capacitated Total Quantity Discount Problem
No full textIn this paper we analyze the procurement problem of a company that needs to purchase a number of products from a set of suppliers to satisfy demand. The suppliers offer total quantity discounts and the company aims at selecting a set of suppliers so to satisfy product demand at minimum purchasing cost. The problem, known as Total Quantity Discount Problem (TQDP), is strongly NP-hard. We study different families of valid inequalities and provide a branch-and-cut approach to solve the capacitated variant of the problem (Capacitated TQDP) where the quantity available for a product from a supplier is limited.
A hybrid algorithm, called HELP (Heuristic Enhancement from LP), is used to provide an initial feasible solution to the exact approach. HELP exploits information provided by the continuous relaxation problem to construct neighborhoods optimally searched through the solution of mixed integer subproblems. A streamlined version of the proposed exact method can optimally solve in a reasonable amount of time
instances with up to 100 suppliers and 500 products, and largely outperforms an existing approach available
in the literature and CPLEX 12.2 that frequently runs out of memory before completing the search
Vehicle 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 branch-and-cut algorithm for the Multi-vehicle Traveling Purchaser Problem with Exclusionary Side Constraints
No full textNew solution approaches for the capacitated supplier selection problem with total quantity discount and activation costs under demand uncertainty
Full text linkThe Nurse Routing Problem with Workload Constraints and Incompatible Services
No full textAmong the health care applications, nursing home services play a central role because of the growing request for long-term home care observed in the recent years. Nursing care providers can guarantee a wide variety of medical and supporting services for not-independent people such as elderly people and disabled itidividuals, highly improving the quality of their life. We propose and study an optimization problem that aims at scheduling the daily services performed by a set of nurses to a set of patients and, simultaneously; at routing the nurses in their visiting tours. The problem is further complicated by considering potential incompatibilities among pairs of services for a single patient in the same day. Through mathemaatical programming techniques, we model the problem as a variant of the multi vehicle traveling purchaser problem (MVTPP) and evaluate different solution strategies. Finally, we focus' on the applicability of a promising branch-and-price solution approach based on a set-covering reformulation of the problem
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 text- …
