Formulação e solução do problema de alocação de veículos estocástico por meio de programação dinâmica aproximada

Abstract

The dynamic and stochastic vehicle allocation problem is a problem with a vast field of applications, which has gained considerable evidence since the emergence of on-demand urban mobility service platforms. In this work, the vehicle allocation problem consists of allocating vehicles to calls that arrive at a call center at random times in order to minimize the waiting time. This problem is formulated as a semi-Markov decision problem. Given that the size of the state space as well as the decision states are sensitive points for obtaining an optimal policy, approximate dynamic programming methods are presented as an alternative way to build approximate decision policies. Therefore, we present a solution to the vehicle allocation problem based on the rollout algorithm, an approximate policy iteration algorithm, that is, given an initial policy, it builds an improved policy based on two steps: policy evaluation and policy improvement. The policies produced by the rollout algorithm are of the lookahead type, which, compared to myopic policies, have the advantage of leading to decisions that balance current and future returns. The rollout algorithm was tested in a simulated environment based on discrete-event simulation, so that the natural process of the semi-Markovian decision process was modeled as a queuing system, controlling the arrival process of new tickets, service of each vehicle, and the discipline of the queue. Thus, the rollout algorithm is based on three basic policies: FIFO, the ticket is chosen prioritizing the waiting time in the queue; NV, the call is chosen prioritizing the distance between vehicles; RANDOM, the call is chosen at random. And it aims to improve the performance of these policies. Overall, the results show that for all these policies, the rollout algorithm was able to produce an average reduction of up to 69% of the average accumulated delay.