نوع مقاله : پژوهشی
نویسندگان
دانشکدهی ریاضی و علوم کامپیوتر، دانشگاه صنعتی امیرکبیر
چکیده
کلیدواژهها
عنوان مقاله [English]
نویسندگان [English]
Stochastic programming under endogenous uncertainty is a new topic in which the time of uncertainty realization is affected by optimization decisions. Development of application areas in this field has been of interest to researchers. Therefore, this paper addresses a novel variant of the vehicle routing problem as a new application of this topic. In this problem, a single vehicle with a limited capacity must serve a set of customers whose demands are uncertain and the actual demands are revealed upon the vehicles arrival to customers. Under some circumstances, the vehicle may be depleted throughout the route before all customers are satisfied; in this case, it needs to return to the depot for replenishment. The objective is to find a policy to satisfy customers demand with the minimum total expected cost. The main point is that this problem is considered from a dynamic viewpoint. Indeed, the route is constructed gradually over multiple stages according to the realized information. For example, the primary decision determines a customer who should be visited in the first stage. Upon the vehicle visiting this customer, his/her actual demand becomes known; then, depending on the realized information, the next decision is to determine a customer who must be visited next, whether directly or after the replenishment at the depot. This process is repeated until all customers are visited. Finally, the vehicle returns to the depot. Clearly, the time of uncertainty realization is decision-dependent and hence, uncertainty is of endogenous nature. Therefore, the scenario tree becomes decision-dependent and nonanticipativity of decisions must be ensured by conditional constraints. This paper formulates the problem as a multi-stage stochastic programming model with endogenous uncertainty. Then, since nonanticipativity constraints constitute a considerably large portion of the total constraints, efficient approaches are proposed to significantly reduce the problem size and improve the solution time. Computational results evaluate the proposed model and approaches on some randomly generated test problems.
کلیدواژهها [English]
)