E N D O G E N O U S U N C E R T A I N D E M A N D S I N V E H I C L E R O U T I N G P R O B L E M
Abstract:
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 vehicle's 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 customer's 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.
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.
Keywords:
Language:
Persian
Published:
Industrial Engineering & Management Sharif, Volume:33 Issue: 1, 2017
Pages:
77 to 84
magiran.com/p1754512
دانلود و مطالعه متن این مقاله با یکی از روشهای زیر امکان پذیر است:
اشتراک شخصی
با عضویت و پرداخت آنلاین حق اشتراک یکساله به مبلغ 1,390,000ريال میتوانید 70 عنوان مطلب دانلود کنید!
اشتراک سازمانی
به کتابخانه دانشگاه یا محل کار خود پیشنهاد کنید تا اشتراک سازمانی این پایگاه را برای دسترسی نامحدود همه کاربران به متن مطالب تهیه نمایند!
توجه!
- حق عضویت دریافتی صرف حمایت از نشریات عضو و نگهداری، تکمیل و توسعه مگیران میشود.
- پرداخت حق اشتراک و دانلود مقالات اجازه بازنشر آن در سایر رسانههای چاپی و دیجیتال را به کاربر نمیدهد.
In order to view content subscription is required
Personal subscription
Subscribe magiran.com for 70 € euros via PayPal and download 70 articles during a year.
Organization subscription
Please contact us to subscribe your university or library for unlimited access!