A Stochastic Single Vehicle Routing Problem with a Predefined Sequence of Customers and Collection of Two Similar Materials

作     者：Kyriakidis, Epaminondas G. Dimitrakos, Theodosis D. Karamatsoukis, Constantinos C. 

作者机构：Athens Univ Econ & Business Dept Stat Patiss 76 Athens 10434 Greece Univ Aegean Dept Math Samos 83200 Greece Hellen Mil Acad Dept Mil Sci Vari 16673 Attica Greece 

出 版 物：《METHODOLOGY AND COMPUTING IN APPLIED PROBABILITY》 (应用概率论的方法与计算)

年 卷 期：2020年第22卷第4期

页      面：1559-1582页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0714[理学-统计学（可授理学、经济学学位）] 0701[理学-数学] 

基　　金：EP-3042-01 

主　　题：Stochastic dynamic programming Vehicle routing problem 

摘      要：We suppose that a vehicle visits N ordered customers in order to collect from them two similar but not identical materials. The actual quantity and the actual type of material that each customer possesses become known only when the vehicle arrives at the customer s location. It is assumed that the vehicle has two compartments. We name these compartments, Compartment 1 and Compartment 2. It is assumed that Compartment 1 is suitable for loading Material 1 and Compartment 2 is suitable for loading Material 2. However it is permitted to load items of Material 1 into Compartment 2 and items of Material 2 into Compartment 1. These actions cause extra costs that are due to extra labor. It is permissible for the vehicle to interrupt its route and go to the depot to unload the items of both materials. The costs for travelling from each customer to the next one and the costs for travelling from each customer to the depot are known. The objective is to find the routing strategy that minimizes the total expected cost among all possible strategies for servicing all customers. A dynamic programming algorithm is designed for the determination of the routing strategy that minimizes the total expected cost among all possible strategies. The structure of optimal routing strategy is characterized by a set of critical numbers for each customer.