Hybrid Value Function Approximation for Solving the Technician Routing Problem with Stochastic Repair Requests

Research output: Contribution to journalArticlepeer-review

Abstract

We investigate the combined planning problem involving the routing of technicians and the stocking of spare parts for servicing geographically distributed repair tasks. The problem incorporates many operational uncertainties, such as future repair requests and the required spare parts to replace malfunctioned components. We model the problem as a sequential decision problem where decisions are made at the end of each day about the next day’s technician route and spare part inventory in the van. We show that exact methods are intractable because of the inherent high-dimensional state, decision, and transition spaces involved. To overcome these challenges, we present two novel algorithmic techniques. First, we suggest a hybrid value function approximation method that combines a genetic search with a graph neural network capable of reasoning, learning, and decision making in high-dimensional, discrete decision spaces. Second, we introduce a unique state-encoding method that employs multiattribute graphs and spatial markers, eliminating the need for manually designed basis functions and allowing efficient learning. We illustrate the general adaptive learning capacity by solving a variety of instance settings without instance-specific hyperparameter tuning. An extensive numerical study demonstrates that our hybrid learning technique outperforms other benchmark policies and adapts well to changes in the environment. We also generate a wide range of insights that not only shed light on the algorithmic components but also offer guidance on how to execute on-site repair tasks more efficiently. The techniques showcased are versatile and hold potential for application in other dynamic and stochastic problems, particularly in the realm of transportation planning.

Original languageEnglish
Pages (from-to)499-519
Number of pages21
JournalTransportation Science
Volume58
Issue number2
DOIs
StatePublished - Mar 2024

Keywords

  • combinatorial decision space
  • graph neural network-based value function approximation
  • multiperiod stochastic problem

Fingerprint

Dive into the research topics of 'Hybrid Value Function Approximation for Solving the Technician Routing Problem with Stochastic Repair Requests'. Together they form a unique fingerprint.

Cite this