كنفرانس بين المللی مهندسی صنايع و سيستم ها

صفحه اصلی / دوازدهمین كنفرانس بين المللی مهندسی صنايع و سيستم ها

Neural Value Function Approximation for Anticipatory Request Acceptance in Stochastic Dynamic Vehicle Routing

نویسندگان :

Behrouz Bahredar¹ Kourosh Eshghi²

1- دانشگاه صنعتی شریف 2- دانشگاه صنعتی شریف

کلمات کلیدی :

approximate dynamic programming،dynamic vehicle routing،neural networks،request acceptance،stochastic requests،value function approximation،reinforcement learning

چکیده :

This paper studies anticipatory request acceptance in a multi-vehicle stochastic dynamic vehicle routing problem. Early requests are known in advance, whereas late requests are revealed dynamically and must be accepted or rejected at sequential decision points. We propose a neural-network value function approximation (NNVFA) that evaluates fleet-size-independent aggregated post-decision states describing workload, route dispersion, temporal flexibility, and spatial coverage. To isolate both the value of explicit anticipation and the value of nonlinear approximation, all policies use the same cheapest-insertion routing procedure, and NNVFA is compared with myopic Greedy, an implicitly anticipatory cost-benefit heuristic, and a linear VFA using the identical state representation and training data. Across 12 instance classes and 250 out-of-sample realizations per class, NNVFA significantly outperforms all benchmarks, improving the average number of accepted late requests by 46.4%, 35.1%, and 20.6%, respectively. Its advantage is largest under high dynamism, spatially dispersed demand, and tighter fleet capacity.