启发式
数学优化
启发式
马尔可夫决策过程
集合(抽象数据类型)
布线(电子设计自动化)
车辆路径问题
计算机科学
上下界
时间范围
过程(计算)
马尔可夫过程
马尔可夫链
数学
机器学习
程序设计语言
操作系统
数学分析
统计
计算机网络
作者
Nicola Secomandi,François Margot
出处
期刊:Operations Research
[Institute for Operations Research and the Management Sciences]
日期:2009-02-01
卷期号:57 (1): 214-230
被引量:139
标识
DOI:10.1287/opre.1080.0520
摘要
We consider the vehicle-routing problem with stochastic demands (VRPSD) under reoptimization. We develop and analyze a finite-horizon Markov decision process (MDP) formulation for the single-vehicle case and establish a partial characterization of the optimal policy. We also propose a heuristic solution methodology for our MDP, named partial reoptimization, based on the idea of restricting attention to a subset of all the possible states and computing an optimal policy on this restricted set of states. We discuss two families of computationally efficient partial reoptimization heuristics and illustrate their performance on a set of instances with up to and including 100 customers. Comparisons with an existing heuristic from the literature and a lower bound computed with complete knowledge of customer demands show that our best partial reoptimization heuristics outperform this heuristic and are on average no more than 10%–13% away from this lower bound, depending on the type of instances.
科研通智能强力驱动
Strongly Powered by AbleSci AI