1,720,998 research outputs found
A hybrid reactive GRASP heuristic for the risk-averse k-traveling repairman problem with profits
No full textThis paper addresses the k-traveling repairman problem with profits and uncertain travel times, a vehicle routing problem aimed at visiting a subset of customers in order to collect a revenue, which is a decreasing function of the uncertain arrival times. The introduction of the arrival time in the objective function instead of the travel time, which is common in most vehicle routing problems, poses compelling computational challenges, emphasized by the incorporation of the stochasticity in travel times. For tackling the solution of the risk-averse k-traveling repairman problem with profits, in this paper is proposed a hybrid heuristic, where a reactive greedy randomized adaptive search procedure is used as a multi-start framework, equipped with an adaptive local search algorithm. The effectiveness of the solution approach is shown through an extensive experimental phase, performed on a set of instances, generated from three sets of benchmark instances containing up to 200 nodes
The selective minimum latency problem under travel time variability: An application to post-disaster assessment operations
No full textIn this paper, we consider a new selective routing problem, where a subset of customers should be serviced by a limited fleet of vehicles with the aim of minimizing the total latency. A service level constraint is added to guarantee that a minimum system performance is achieved. Assuming that the travel times are uncertain, we address the problem through a mean-risk approach. The inclusion of risk in the objective function makes the problem computationally challenging. To solve it, we propose an efficient heuristic, relying on a variable neighbourhood search mechanism, able to strike the balance between service level and latency. A detailed discussion of the model, which includes simulation tests and a sensitivity analysis, is carried out to illustrate the applicability of our approach in a post-disaster scenario, taking as a case study the Haiti earthquake in 2010. Additional computational experiments show that the proposed heuristic is effective for this difficult problem and often matches optimal solutions for small and medium-scale benchmark instances
A heuristic Approach for the k-Traveling Repairman Problem with Profits under Uncertainty
No full textThis paper addresses the k-traveling repairman problem with profits under uncertain travel times, a new vehicle routing problem aimed at visiting a subset of customers in order to collect a revenue, defined as decreasing function of the uncertain arrival times. We adopt a risk-averse approach, enabling the decision maker to manage and control risk, and develop a mean-risk model in which only the first and the second moment of the travel times distribution are required to be known. We propose an adaptive local search heuristic in which, in each iteration, a Greedy Randomized Adaptive Search Procedure is used to generate the initial solution. The effectiveness of the solution approach is shown by the computational experiments performed on a set of instances
Solving Stochastic Linear Programs with Restricted Recourse using Interior Point Methods
No full textOptimal Capacity Allocation in Multi-Auction Electricity Markets under Uncertainty
No full textThe advent of competitive markets confronts each producer with the problem of optimally allocating his
energy/capacity so as to maximize his pro$ts. The multiplicity of auctions in electricity markets andthe nontrivial constraints imposedby technical andbid ding rules make the problem of crucial importance andd i/cult
to model and solve. Further di/culties are represented by the dynamic and stochastic natures that characterize
the decision process. We formulate the problem as a multi-stage mixed-integer stochastic optimization model
under the assumption that the seller is a price taker. We validate the e2ectiveness of the proposed model on
a representative test problem
Parallel Algorithms to Solve Two-Stage Stochastic Linear Programs with Robustness Constraints
No full text
The Traveling Purchaser Problem Under Uncertainty
No full textThe Traveling Purchaser Problem (TPP) is an interesting procurement and
routing NP-hard problem that finds application in several domains. The problem
aims at determining a tour starting at and ending to the depot while visiting
a subset of markets in such a way that a demand for each product is satisfied
and that the cost globally spent for purchasing the products and visiting the
markets is minimized. The deterministic TPP ignores the uncertain nature of
some parameters involved in the model, thus typically providing recommendations
with limited practical application. While the deterministic version of the
TPP has been largely studied (e.g. see [1]), very few contributions exist in the
literature for the TPP under uncertainty [2]. This work proposes a scenariobased
stochastic and capacitated version of the TPP which explicitly takes into
account uncertainty in prices and/or products availability. Injecting stochastic
elements in the model allows us to manage closely real-life applications. We cast
the model within a two-stage stochastic paradigm based on a distinction between
the first-stage variables, which have to be decided upon before the outcomes of
the stochastic variables are observed, and the second stage variables which have
to be decided after the uncertainty is resolved. To efficiently solve the problem,
we develop a tailored heuristic approach designed to exploit the specific problem
structure. Encouraging preliminary computational results are provided.
References:
[1] G. Laporte, J. Riera-Ledesma, J.J. Salazar-Gonzalez, A branch-and-cut
algorithm for the undirected Traveling Purchaser Problem, Operation Research
51(6), pp. 940-951 (2003).
[2] S. Kang, Y. Ouyang, The traveling purchaser problem with stochastic prices:
exact and approximate algorithms, European Journal of Operational Research
209(3), pp. 265-272 (2011)
A Fix and Relax heuristic for a stochastic Lot-Sizing problem
No full textThis paper addresses a particular stochastic lot-sizing and scheduling problem. The evolution
of the uncertain parameters is modelled by means of a scenario tree and the resulting model is a multistage
stochastic mixed-integer program. We develop a heuristic approach that exploits the specific structure of the
problem. The computational experiments carried out on a large set of instances have shown that the approach
provides good quality solutions in a reasonable amount of time
- …
