A dynamic and probabilistic orienteering problem
| Autor: | Carlo Filippi, Claudia Archetti, Enrico Angelelli, Michele Vindigni |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2021 |
| Předmět: |
Mathematical optimization
General Computer Science Computer science Heuristic (computer science) Random requests Probabilistic logic Orienteering Interval (mathematics) Management Science and Operations Research Dynamic vehicle routing Reduction (complexity) Heuristics Orienteering problem Routing Modeling and Simulation Graph (abstract data type) Markov decision process Routing (electronic design automation) |
| Popis: | We consider an online version of the orienteering problem, where stochastic service requests arise during a first time interval from customers located on the nodes of a graph. Every request must be accepted/rejected in real time. Later, a vehicle must visit the accepted customers during a second time interval. Each accepted request implies a prize, depending on the customer, and a service cost, depending on the routing decisions. Moreover, an accepted request implies a reduction of the routing time available for possible future requests. Each acceptance/rejection decision is made to maximize the expected profit, i.e., the difference between expected prices and expected service costs. We formulate the problem as a Markov Decision Process and derive analytical expressions for the transition probabilities and the optimal policy. Since an exact policy computation is intractable, we design and test several heuristic approaches, including static approximation, simple greedy (non-anticipatory) methods, Sample Average Approximation (SAA) of the objective function using Monte Carlo sampling of future events. We perform extensive computational tests on the proposed algorithms and discuss the pros and cons of the different methods. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|