Operations Research · 1993 · 112 citations · 18 references
ManagementIndustrial EngineeringOperations ManagementMarkov Decision ProcessesOptimizationSchedulingDynamic SchedulingScheduling TheoryStochastic OptimizationStochastic ProgrammingStochastic SchedulingVehicle SchedulingDelivery ProblemDelivery Vehicle SchedulingDispatch ModelingDispatchingDispatching AlgorithmsHeuristic ApproachMarkov Decision ModelsStochastic Vehicle Scheduling
We describe a dynamic and stochastic vehicle dispatching problem called the delivery dispatching problem. This problem is modeled as a Markov decision process. Because exact solution of this model is impractical, we adopt a heuristic approach for handling the problem. The heuristic is based in part on a decomposition of the problem by customer, where customer subproblems generate penalty functions that are applied in a master dispatching problem. We describe how to compute bounds on the algorithm's performance, and apply it to several examples with good results.
18