Optimizing the Service Card in Multi-Depot, Multi-Product and Multi-Level Vehicle Routing Problems with the Aim of Minimizing the Total Distribution Costs

M. Mehdi Sepehri & Mehrdad Kargari

M.Mehdi Sepehri, Tarbiat Modares University
Mehrdad Kargari, Tarbiat Modares University

Keywords ABSTRACT

multi-depot, multi-product and multi-level vehicle routing, minimizing distribution costs, Lagrange coefficients, network models,
resource allocation and resource leveling, service card Optimizing the service card in multi-depot, multi-product and multi-level vehicle routing problem is one of the most important and at the same time, the most complex problems in the transportation problems contexts. Numerous exact heuristic and meta-heuristic algorithms have been developed for different vehicle routing problems. In this paper, a binary linear programming (BLP) based model for optimizing the service card in multi-depot, multi-product and multi-level vehicle routing problems with the aim of minimizing the total distribution costs has been proposed. In other words, the purpose of this paper is to determine the optimum transportation for each product in vehicle routing problems for every route, grape and level with minimum distribution costs. Then, an effective algorithm has been developed to solve the problem. The proposed algorithm using the limited resource leveling based on the Lagrange coefficients; transform the multiproduct problem into multiple single-product problems. When each mathematical model for single product vehicle routing problems is solved, the assigned capacity and the required capacity values for each product are compared and then the available and total capacity is calculated. Finally, resource leveling and service card optimization processes are applied to all single-product problems. Therefore, after several steps if no considerable improvement is observed in the solution, then the optimal solution is achieved for the original problem. Design of experiments and validation tests used in the paper indicate the optimal utilization of the limited resources and a considerable reduction in the total distribution costs. Validity of the proposed algorithm against the binary linear programming model has been verified at 95% and computational time has been reduced by 5 times.
æèíîçæŶƬūæƵŹŚưƃ ŶǀƫƺţŢƿźƿŶƯƹƖƿŚƴƇƾſŶƴƸƯƾƬƬưƫřƲǀŝƶƿźƄƳ’

ŶƴģƾŰƐſŶƴģƾŝŚƿźǀƀƯƪŗŚƀƯŹŵžƿƹźſŶŞſƾŝŚƿƶƴǀƸŝ
ƽŚƷƶƴƿżƷƱŵƺưƳƪƣřŶůƝŶƷŚŝƶǀƬƤƳƪƿŚſƹƾƷŚĭŹřźƣŶƴģƹƾƫƺƈŰƯ
ƖƿŻƺţ
ƽźĭŹŚƧŵřŵźƸƯƹÎƽźƸĜſƽŶƸƯŶưŰƯ
íííçêƩƺƇƹŲƿŹŚţ íîæèæŜƿƺƈţŲƿŹŚţ
mehdi.sepehri@modares.ac.irŽŹŶƯŢǀŝźţƵŚĮƄƳřŵƖƿŚƴƇƾſŶƴƸƯƵŶƨƄƳřŵŹŚǀƄƳřŵƽźƸĜſƽŶƸƯŶưŰƯźŤƧŵ
m_kargari@modares.ac.irŽŹŶƯŢǀŝźţƵŚĮƄƳřŵƖƿŚƴƇƾſŶƴƸƯƽźŤƧŵƽƺŬƄƳřŵƽźĭŹŚƧŵřŵźƸƯ
ƽźĭŹŚƧŵřŵźƸƯƹƽźƸĜſƽŶƸƯŶưŰƯƹƾƫƺƈŰƯŶƴģƾŰƐſŶƴģƾŝŚƿźǀƀƯƪŗŚƀƯŹŵžƿƹźſŶŞſƾŝŚƿƶƴǀƸŝêå
ƵŶǀĪģƽŶǀƬĩšŚưƬĩ

ƾƫƺƈŰƯŶƴģƾƷŚĮŤƀƿřŶƴģƶǀƬƤƳƪƿŚſƹƾŝŚƿźǀƀƯƪƿŚƀƯžƿƹźſŶŞſƾŝŚƿƶƴǀƸŝƕƺƋƺƯ óƾƷŚĮŤƀƿřŶƴģƶǀƬƤƳƪƿŚſƹƾŝŚƿźǀƀƯ ƵŻƺůŹŵƽźǀĭƮǀưƈţƪŗŚƀƯƲƿźţƪĪƄƯƩŚůƲǀƗŹŵƹƲƿźţƮƸƯŻřƾƨƿƾŰƐſŶƴģƹ ƾŰƐſŶƴģƹƾƫƺƈŰƯŶƴģ ƽřźŝƾƗƺƴŤƯƽŹŚƨŤŝřơƺƟƹƽŹŚƨŤŝřƢǀƣŵƽŚƷƮŤƿŹƺĮƫřƱƺƴĩŚţŶƃŚŞǀƯƪƤƳƹƪưůƪŗŚƀƯ ƖƿŻƺţƽŚƷƶƴƿżƷƱŵƺưƳƪƣřŶů
ƶƯŚƳźŝƩŶƯƦƿƶƫŚƤƯƲƿřŹŵŢſřƵŶƃƶŗřŹřƶǀƬƤƳƪƿŚſƹƾŝŚƿźǀƀƯƪŗŚƀƯƞƬŤŴƯƽŚƸƫŶƯƪů ƽřƶƨŞƃƽŚƸƫŶƯĦƳřźĭLJŜƿřźƋ ƶǀƬƤƳƪƿŚſƹƾŝŚƿźǀƀƯƪƿŚƀƯŹŵžƿƹźſŶŞſƾŝŚƿƶƴǀƸŝƽřźŝ(BLP)ƦƿƹźƠƇƾƐųƽżƿŹ ƖŝŚƴƯŮǀƐƀţƹƆǀƈŴţ ƶŗřŹřƖƿŻƺţƽŚƷƶƴƿżƷƱŵƺưƳƪƣřŶůƝŶƷŚŝƾŰƐſŶƴģƹƾƫƺƈŰƯŶƴģóƾƷŚĮŤƀƿřŶƴģ žƿƹźſŶŞſ
ŻřĨƿźƷƽřźŝƪƤƳƹƪưůƶƴǀƸŝŢŞƀƳƱřżǀƯƲǀǀƘţƶƫŚƤƯƲƿřƝŶƷźŤƸŝšŹŚŞƘŝŢſřƵŶƃ ƖƿŻƺţ ƶƴƿżƷ ƪƣřŶů Śŝ ŭƺƐſ ƹ ƾůřƺƳ ŚƷźǀƀƯ Żř ĨƿźƷ ƽřźŝ ƶǀƬƤƳ ƪƿŚſƹ Źŵ šLJƺƈŰƯ
ŻřƵŵŚƠŤſřŚŝƮŤƿŹƺĮƫřƲƿřŶƿŵźĭƾůřźƏřŹŚƧƮŤƿŹƺĮƫřƦƿƩŶƯƲƿřƪůƽřźŝžĜſŶƃŚŞǀƯ ƶƬŘƀƯŶƴģƶŝřŹƾƫƺƈŰƯŶƴģƾŝŚƿźǀƀƯƶƬŘƀƯĦƳřźĭLJŜƿřźƋƶƿŚěźŝŵƹŶŰƯƖŝŚƴƯƆǀƈŴţ
ƾƫƺƈŰƯĨţƾŝŚƿźǀƀƯƪŗŚƀƯŻřĨƿźƷƾƋŚƿŹƩŶƯƪůŻřŶƘŝŶƴĪǀƯƪƿŶŞţ ƾƫƺƈŰƯƦţ ƵŶƳŚưǀƣŚŝŢǀƟźƓƱřżǀƯšLJƺƈŰƯŻřƦƿźƷŻŚǀƳŵŹƺƯƹƵŶƃƵŵřŵƆǀƈŴţŢǀƟźƓƶƀƿŚƤƯŚŝ ƪŗŚƀƯ ƲǀŝŹŵ žƿƹźſ ŶŞſ ƾŝŚƿƶƴǀƸŝ ƹ ƖŝŚƴƯ ŮǀƐƀţ šŚǀƬưƗ žĜſ ƹ ƶŞſŚŰƯ řŹ ƪƧ ƹ ƽŚƷ ŢǀƟźƓ ŮǀƐƀţ ƶƬůźƯ Ŷƴģ ŻřŶƘŝ ŽŚſř Ʋƿřźŝ ŵƺƄǀƯ ƭŚŬƳř ƾƫƺƈŰƯ Ʀţ ƾŝŚƿźǀƀƯ ƾƬƇřƶƬŘƀƯśřƺūŵƺƄƳƪƇŚůƶƬŘƀƯśřƺūŹŵƾƸūƺţƪŝŚƣŵƺŞƸŝƶƧƾţŹƺƇŹŵƵŶƳŚưǀƣŚŝ ƶƴǀƸŝƵŵŚƠŤſřźĮƳŚǀŝƶƫŚƤƯƲƿřŹŵƵŶƃƭŚŬƳřƾŬƴſŹŚŞŤƗřƹšŚƄƿŚƯŻōƾůřźƏŢſřƵŶƃƪƇŚů
ŹŚŞŤƗřšŚƄƿŚƯŻōƲƿřŶƃŚŞǀƯƖƿŻƺţƽŚƷƶƴƿżƷƶūƺţƪŝŚƣƂƷŚƧƹśŚǀưƧƖŝŚƴƯŻřƁƹŹƲƿř
ŶǀŗŚţŶƇŹŵîêŮƐſŹŵƦƿƹźƠƇƾƐųƽżƿŹƶƯŚƳźŝƩŶƯƶŝŢŞƀƳřŹƵŶƃƾůřźƏƮŤƿŹƺĮƫř ŢſřƵŵřŵƂƷŚƧźŝřźŝêƱřżǀưŝřŹƪŗŚƀƯƪůƱŚƯŻƹƵŵƺưƳ

ƱřƺŤǀƯƾƬƧŹƺƐŝřŹƶǀƬƤƳƪƿŚſƹƾŝŚƿźǀƀƯŹŵƾŤƿźƿŶƯšŚưǀưƈţ ƵŚºţƺƧƹšŶƯƱŚǀƯšŶƯŶƴƬŝƽźǀĭƮǀưƈţƪŗŚƀƯƶŤſŵƶſŹŵ źŤƄǀŝŶǀƧŚţLJƺưƘƯšŶƯŶƴƬŝƪŗŚƀƯŹŵŵƺưƳƽŶƴŝƮǀƀƤţšŶƯ ƽŚ ƸƿźǀĭƮǀưƈ ţƪƯŚ ƃƹƵŵƺ ŝƾ ƬƧƽŚ ƷŻŚǀƳƾ ƴǀŝƂǀ ěź ŝ šřżºǀƸŬţśŚŴŤƳřƖƿŻƺţƽŚƷŹŚŞƳřƪŰƯśŚŴŤƳřƪǀŞƣŻřƦƿĦţřźŤſř ƹŶºƿŶūƽŚƷźǀƀºƯŵŚŬƿřšLJƺƈŰƯƕƺƳśŚŴŤƳřƖƿŻƺţŶƴƿōźƟƹ šŶºƯƱŚºǀƯƽżºƿŹƶºƯŚƳźŝŹŵŢºſřƱŚƿźŤƄƯƽŚƋŚƤţƾƴǀŝƂǀě ƖƿŻƺţƽŚƷƶŤƃŚŞƳřƲǀǀƘţƱŚƿźŤƄƯƽŶƴŝƶŤſŵƱƺĤưƷƽŵŹřƺƯ
ƕƺºưŬƯƱŵƺºưƳƪƣřŶºůƝŶºƷŚºŝƶǀƬƤƳƪƿŚſƹŻřƦƿźƷƾŝŚƿźǀƀƯ šŶƯƵŚţƺƧƽżƿŹƶƯŚƳźŝŹŵŵźǀĮǀƯŹřźƣźƔƳŵŹƺƯƖƿŻƺţƽŚƷƶƴƿżƷ ƾƫřƺºţƲǀºǀƘţƶºƳřŻƹŹƪƤƳƹƪưůšŚǀƬưƗƽŶƴŞƳŚƯŻƱƺģƾƬƿŚƀƯ
ŵŹƺºƯƖºƿŻƺţšŚºǀƬưƗƶºŝƪƿŚºſƹƆǀƈŴţƹƪƤƳƹƪưůšŚǀƬưƗ
>è@ŶƃŚŞǀƯƶūƺţ źǀƀƯƪƿŚƀƯŹŵžƿƹźſŶŞſƾŝŚƿƶƴǀƸŝƕƺƋƺƯƶŝƲŤųřŵźěƵŻƹźƯř ŹƺŰƯƩƺůŶƃŚŝŹřżƟřŢŴſƶūƺŤƯƶƨƳōŻřƪŞƣƶǀƬƤƳƪƿŚſƹƾŝŚƿ ƹ ƽŹƹ ƵźƸŝ ƂƿřżƟř ŶƿŶū ƽŚƸƃƹŹ ƾƴƘƿ ŶƳżǀƯ Źƹŵ ŹřżƟř ƭźƳ źƨƠŝƶƨƳōŻřƪŞƣƹŶƳřŵƾưƳƖŝŚƴƯƂƿřżƟřŹŵŚƟźƇřŹƶƴƿżƷƂƷŚƧ ƵĦƿƹŢǀưƷřŶƴƃŚŝŶƿŶūƖŝŚƴƯƽřźŝƾƟŚƋřƽŹřŸĭƶƿŚƯźſƹƶƘſƺţ
Ţſř ƪŗŚƣ ƾſźŤſŵ Źŵ ƖŝŚƴƯ Żř źŤƸŝ ƶģźƷ ƽźǀĭŹŚƨŝ ƽřźŝ ƽř ƾŝŚƿźǀƀƯ Źŵ ƶƧ ƾŤƿźƿŶƯ šŚưǀưƈţ Żř ƂŴŝ Ʊō źŤƸŝ šŹŚŞƘŝ ƶƧ Ƶŵƺŝ šŶƯ ƱŚǀƯ šŚưǀưƈţŢſřźƔƳ ŵŹƺƯ źŤƄǀŝ ƶǀƬƤƳ ƪƿŚſƹ ƶƯŶƤƯæ
ŵŹƺºƯƱƺƴƧŚţŻŚŝźƿŵŻřƱōŢǀưƷřƹƶǀƬƤƳƪƿŚſƹƾŝŚƿźǀƀƯƕƺƋƺƯ ŚºƷƮŤƀºǀſƲƿźţƩƺưƘƯŢſřƵŵƺŝƱŚƷƹĦěƂƳřŵƹƲǀƤƤŰƯƶūƺţ ŶºƴģƶºǀƬƤƳƪƿŚºſƹƾŝŚºƿźǀƀºƯƶƬŘƀºƯƖºƿŻƺţƹƂŴěƽŚǀƳŵŹŵ
ƱŵƺºưƳƪƣřŶºůƝŶƷŚŝƾŰƐſŶƴģƹƾƫƺƈŰƯŶƴģóƾƷŚĮŤƀƿř
>æ@ŶƃŚŝƾƯƖƿŻƺţƽŚƷƶƴƿżƷ
ŻřƶºƴǀƸŝƵŵŚƠŤſřƱōƝŶƷƶƧŢſřƾŤǀƫŚƘƟƶǀƬƤƳƪƿŚſƹƾŝŚƿźǀƀƯ
ƶºŝƲǀºƘƯŶºƗƺƯŹŵƱŚƿźŤƄƯƽŚƋŚƤţƲǀƯŚţŹƺƔƴưŝƖƿŻƺţƖŝŚƴƯ
ƲºƿřŹŵŶºƃŚŝƾºƯƶºƴƿżƷƪƣřŶºůŚºŝƲǀƘƯƱŚƨƯŹŵƹƲǀƘƯƱřżǀƯ ƽźºſƦºƿƭŚºŬƳřƶŝŻŚǀƳƽźŤƄƯƶŝƩƺƈŰƯźƷƪƿƺŰţŚƷƮŤƀǀſ ƪºưůźĮƳŚºǀŝƮŤƀǀſŻřƶƬůźƯźƷŢſřƞƬŤŴƯƪůřźƯŹŵšŚǀƬưƗ ƶºƐƤƳƶºŝƶºƐƤƳƦºƿŻřƲǀºƃŚƯŶƴģŚƿƦƿƎſƺţLJŚƧŶƴģŚƿƦƿ
ƱŚƿźŤƄƯřŹLJŚƧšŚǀƬưƗƭŚŬƳřƶƬůźƯźƷƮŤƀǀſƲƿřŹŵŢſřźĮƿŵ
ŶƴƨǀƯźŤƨƿŵżƳƾƿŚƸƳ ƖºƿŻƺţƽŚºƷƶºƴƿżƷƩźºŤƴƧƽŚºƸƷřŹƲƿźºŤƸŝƹƲƿźŤưƸƯŻřƾƨƿ ƽřźºŝŵƹŶºŰƯƖŝŚƴƯƆǀƈŴţšŚǀƬưƗŵŹƺƯŹŵŮǀŰƇƽźǀĭƮǀưƈţ
ŭƺƐºſŚƷźǀƀƯŹŵšLJƺƈŰƯŻřƦƿźƷƽřźŝƖƿŻƺţƶŤƃŚŞƳřƲǀǀƘţ ƭŶºƗƶǀƬƤƳƪƿŚſƹƾŝŚƿźǀƀƯƽŚƸƫŶƯŹŵřźƿŻŢſřƞƬŤŴƯƾůřƺƳƹ ƽŚƷŹŚŞƳřŹŵƽŵƺūƺƯƂƿřżƟřƶǀƬƤƳƪƿŚſƹŢǀƟźƓŻřƪƯŚƧƵŵŚƠŤſř
ƮŤƀǀſƶŝřŹƽŵŚƿŻƶƴƿżƷƾƳLJƺƏƾŝŚƿźǀƀƯƹƖƿŻƺţƞƬŤŴƯƪůřźƯ
>ç@ŶƴƨǀƯƪǀưŰţ
êæƽźĭŹŚƧŵřŵźƸƯƹƽźƸĜſƽŶƸƯŶưŰƯƹƾƫƺƈŰƯŶƴģƾŰƐſŶƴģƾŝŚƿźǀƀƯƪŗŚƀƯŹŵžƿƹźſŶŞſƾŝŚƿƶƴǀƸŝ
ƮǀƀƤţ źƿŻ ƶŤſŵ ƶſ ƶŝ ƾƬƧŹƺƐŝ ƶǀƬƤƳ ƪƿŚſƹ ƾŝŚƿźǀƀƯ ƶƬŘƀƯ
ŶƳƺƄǀƯ
ƱŚĭŶƴƴƧƲǀƯŚţŻřŻŚǀƳŵŹƺƯšŚƘƐƣƹƶǀƫƹřŵřƺƯƲǀƯŚţ 
ƶƳŚųŹŚƧƱƹŹŵŹŵƶŤųŚſƶưǀƳšŚƘƐƣƹŵřƺƯƾƿŚŬŝŚū 
ƱŚƿźŤƄƯƲǀŝŹŵƾƿŚƸƳšLJƺƈŰƯƖƿŻƺţƹƂŴě 
ƵŶƃ ƭŚưţ Ţưǀƣ ŶƇŹŵ 1050 Ʋǀŝ ƪƤƳƹ ƪưů ƽŚƷƶƴƿżƷ ƪưů ƽŚƷ ƶƴƿżƷ ƂƷŚƧ ƲƿřźŝŚƴŝ  ŶƷŶǀƯ ƪǀƨƄţ řŹ šLJƺƈŰƯ ŶƷřƺųšLJƺƈŰƯƵŶƃƭŚưţŢưǀƣƂƷŚƧźŝƾƸūƺţƪŝŚƣźǀŧŚţƪƤƳƹ ŵŹřƺƯ Żř ƦƿźƷŹŵ ŮǀŰƇ šŚưǀưƈţ Ÿųř ƶƧ ŚŬƳō Żř >ëé@Ţƃřŵ Ʊō ƽŹƹ ƵźƸŝ ƹ ƪƤƳƹ ƪưů ƮŤƀǀſ ŵźƨƬưƗ ƂƿřżƟř ƽƹŹźŝ ơƺƟ ƖƿŻƺţƹƂŴěƽŚƸŤƧźƃŢŝŚƣŹŢǀƬŝŚƣƹƾƿŚƳřƺţŹŵƹƵŵƺŝŹřŸĭźǀŧŚţ ƪůƹƽŻŚƀƫŶƯƽŚƸƃƹŹŵƺŞƸŝƹƶƘſƺţŵŹřŵƽřƵŶƴƴƧƲǀǀƘţƂƤƳ ƶǀƬƤƳƪƿŚſƹƾŝŚƿźǀƀƯƪŗŚƀƯŹŵžƿƹźſŶǀſƾŝŚƿƶƴǀƸŝƽŚƸƫŶƯ
ƱŵƺưƳƪƣřŶůƝŶƷŚŝƾŰƐſŶƴģƹƾƫƺƈŰƯŶƴģƾƷŚĮŤƀƿřŶƴģ ƾſŹźŝ ŵŹƺƯ ƶƫŚƤƯ ƲƿřŹŵ ƹ ƶŤƃřŵ ƽŵŚƿŻ ŢǀưƷř ƖƿŻƺţ ƽŚƷƶƴƿżƷ ƾŝŚƿźǀƀƯ ƪŗŚƀƯ Źŵ ƾŤƿźƿŶƯ šŶƯ ƱŚǀƯ šŚưǀưƈţ ŵźǀĭƾƯ Źřźƣ Źŵ ƮƸƯ šŚưǀưƈţ ŶƃŚŞǀƯ ƽźŤƄǀŝ ŢǀưƷř ƽřŹřŵ ƶǀƬƤƳ ƪƿŚſƹ ƲǀǀƘţƱŚƿźŤƄƯƽŶƴŝƶŤſŵƪƯŚƃƢǀƤŰţƲƿřƾŝŚƿźǀƀƯƪŗŚƀƯ
ƝŶƷ Śŝ ƶǀƬƤƳ ƪƿŚſƹ Żř ƦƿźƷ ƾŝŚƿźǀƀƯ ƹ ƖƿŻƺţ ƽŚƷ ƶŤƃŚŞƳř ƽŚƸƫŶƯŹŵřźƿŻŶƃŚŝƾƯƖƿŻƺţƽŚƷƶƴƿżƷƕƺưŬƯƱŵƺưƳƪƣřŶů Żř ŶƘŝ ƾŰƐſŶƴģ ƹ ƾƫƺƈŰƯ Ŷƴģ óƾƷŚĮŤƀƿř Ŷƴģ ƾŝŚƿźǀƀƯ
ƖƿŻƺţ ƶŤƃŚŞƳř ƵŻřŶƳř ƲǀǀƘţ ƶŝ ŢŝƺƳ ƱŚƿźŤƄƯ ƽŶƴŝƶƃƺų šŚǀƬưƗ ƞƬŤŴƯ ƾůřƺƳ ƹ ŭƺƐſ ŚƷźǀƀƯ Źŵ šLJƺƈŰƯ Żř Ʀƿ źƷ ƽřźŝ ƪƇřƦƿƱřƺƴƘŝ>ì@ŵƺƄǀƯƭŚŬƳřƾŝŚƿźǀƀƯšŚǀƬưƗžĜſŵƺƄǀƯ ƱŚƯŻ ŶƃŚŝ źŤĭŹżŝ ƪƤƳƹ ƪưů ƪƿŚſƹ ƶģźƷ ŢƠĭ ƱřƺţƾƯ ƾƬƧ
ŶŝŚŞǀƯƂƷŚƧźǀƀƯƾƏƱŚƯŻƹƶŤƟŚƿƂƿřżƟřƽŻřŶƳřŹŚŝƹƽźǀĭŹŚŝ ƶŤƃŚŞƳř ƲǀǀƘţ ƽŶƴŝ ƶƃƺų ƽŚƷŢſŚǀſ ƢǀƠƬţ ŽŚſř Ʋƿřźŝ >í@
ƹŭƺƐſƪůřźƯŻřƦƿźƷŹŵƶǀƬƤƳƪƿŚſƹƾŝŚƿźǀƀƯƹƖƿŻƺţƽŚƷ
>î@ŶƴƧƾƯƪƣřŶůřŹƖƿŻƺţƮŤƀǀſƽŚƷƶƴƿżƷƞƬŤŴƯƾůřƺƳ
ƽřźºŝŶºƿŶŰţƹśŚƘƄƳřƮŤƿŹƺĮƫřƦƿ>æå@ƱřŹŚƨưƷƹšŹƺěLJ 
ŶºƳŵƺưƳƽŹƹōŵŚºƿƱŚƄƿřŶƳŵƺưƳƶŗřŹřMDVRPƪŗŚƀƯƪů
ŜºſŚƴƯƦºģƺƧƪŗŚƀºƯƪºůƽřźºŝƎºƤƟŚƷƮŤƿŹƺĮƫřƲƿřƶƧ
ŶƴŤƀƷ
ƭŚºųŵřƺºƯƪºƤƳƹƪºưůƶƬŘƀºƯ>ææ@ƭŚųŹŚƯƹŢſřźĤǀƯŚſ 
Ŝ ƫŚƣŹŵřŹšŚƀ ǀſŚţŻřƽřƶ ƗƺưŬƯƶ ŝƵŚĮŤƀ ƿřƲƿŶ ƴģŻř
ŶƳŵźƧƶƫƺƯźƟMDVRP
ƽřźºŝƽŻŚºſƶƴǀƸŝƶƿLJƶſƩŶƯƦƿ>æç@ƱřŹŚƨưƷƹƱƺŤſřƹ 
ŶƳŵƺưƳƶŗřŹřƽŶǀƫƺţšŚŬƳŚųŹŚƧšLJƺƈŰƯƪƤƳƹƪưůƮŤƀǀſ
ƝŸºůŚºŝƶºƿLJƶºſƩŶºƯƪůƽřźŝ>æè@ƱřŹŚƨưƷƹŹŚǀŞƯŚƳ 
řŹƱōžĜºſƹƪƿŶŞţƶƿLJƹŵƩŶƯƶŝřŹƶƬŘƀƯƾƳŚǀƯƽŚƷŹŚŞƳř
ƶºƿLJŶƴģƽŚƸƫŶƯƶưƷƶƧŶƴŤƃřŵƵŶǀƤƗƱŚƄƿřŶƳŵƺưƳƪů ŶƃŚŞǀƯƪůƪŝŚƣƶƿLJƹŵƽŚƸƫŶƯŚŝ ƾŝŚƿźǀƀƯƹƖƿŻƺţƽŚƷƶŤƃŚŞƳřƱřżǀƯƲǀǀƘţƱŚƿźŤƄƯƽŶƴŝƶŤſŵ Żř ŶƘŝ ƖƿŻƺţ ƽŚƷƮŤƀǀſ Źŵ řźƿŻ Ţſř Ʊō ƮƸƯ ƪŗŚƀƯ ƶƬưū Żř ƽƹŹźŝ šŚǀƬưƗ ƪưů šřżǀƸŬţ ƹ ƱŚƿźŤƄƯ ƽŚƋŚƤţ ƲǀǀƘţ šŹƺƇ ƾŝŚƿźǀƀƯ ƹ ƖƿŻƺţ ƶŤƃŚŞƳř ƱřżǀƯ ƱŚƿźŤƄƯ ƽŶƴŝƶŤſŵ ƹ ƩźŤƴƧ ƽŚƸƷřŹ ƲƿźŤƸŝ ƹ ƲƿźŤưƸƯ Żř ƾƨƿ ŽŚſř Ʋƿřźŝ ŵźǀĮǀƯ ƽŶƴŝ ƶŤſŵ ƅƺƈųŹŵ ƽźǀĭ Ʈǀưƈţ ƖƿŻƺţ ƽŚƷƶƴƿżƷ ƂƷŚƧ
ŻřƦƿźƷƽřźŝŮǀŰƇƾŝŚƿźǀƀƯƹƖƿŻƺţƶŤƃŚŞƳřƲǀǀƘţƱŚƿźŤƄƯ
ŶƃŚŝƾƯŵƺƿźěźƷŹŵƶǀƬƤƳƪƿŚſƹ ŚţƽżƧźƯŹŚŞƳřƲǀŝźǀƀƯŢǀưƷřƶǀƬƤƳƪƿŚſƹƾŝŚƿźǀƀƯƪŗŚƀƯŹŵ ƹ ŹŚƨƃō ŹŚǀƀŝ ƱŚƿźŤƄƯ ŹŚŞƳř Śţ ƾƳŚǀƯ ƽŚƷŹŚŞƳř ƹ ƾƳŚǀƯ ƽŚƷŹŚŞƳř
ŶƴƨǀƯƪǀưŰţƮŤƀǀſźŝƽŵŚƿŻƶƴƿżƷLJƺưƘƯƹŢſřźƿŸěŚƳŹŚƨƳř Ţſř ŹřŵŹƺųźŝ ƽř ƵĦƿƹ ŢǀưƷř Żř ŚƷźǀƀƯ Ʋƿř ƩźŤƴƧ řŸƫ ƹ
ƱŚƿźŤƄƯŶƿŚŝƾŝŚƿźǀƀƯšŚǀƬưƗŻřƪŞƣƪƇřƦƿƱřƺƴƘŝƲǀƴĤưƷ šŚǀƬưƗ ƖƿŻƺţ ƶŤƃŚŞƳř ƱřżǀƯ ƲǀǀƘţ Żř žě ƹ ƵŶƃ ƽŶƴŝ ƶƤŞƏ ŹŵŚŝƶƧƮǀŤƀƷƾƿŚƷźǀƀƯƩŚŞƳŶŝŚƯƲƿřźŝŚƴŝŵƺƃƭŚŬƳřƾŝŚƿźǀƀƯ ƽŚƋŚƤţ ƶƴƿżƷ ƪƣřŶů Śŝ ƪưů ƪƿŚſƹ ŢƿŵƹŶŰƯ ƲŤƟźĭ źƔƳ ƽƹŹźŝ ŶǀƧŚţ ƢǀƤŰţ ƲƿřŹŵ ŶƴƧ ƲǀƯŚţ ŹźƤƯŶƗƺƯ Źŵ řŹ ƱŚƿźŤƄƯ ƱŚƿźŤƄƯ ƽŶƴŝ ƶƤŞƏ ƽƹŹ ƅŚų ŹƺƐŝ ƹ šŶƯ ƱŚǀƯ ƽżƿŹ ƶƯŚƳźŝ ƾŝŚƿźǀƀƯ ƶƬŘƀƯ ƪů Ţſř ƾŝŚƿźǀƀƯ ƹ ƖƿŻƺţ ƶŤƃŚŞƳř ƲǀǀƘţ ƱŚƿźŤƄƯ ƽŶƴŝ ƶƤŞƏ  ƱŚƿźŤƄƯ ƽŚƋŚƤţ ƾƴǀŝ Ƃǀě ƭżƬŤƀƯ ƾŝŚƿźǀƀƯ ƹ ƖƿŻƺţ ƶŤƃŚŞƳř ƲǀǀƘţ ƪƤƳ ƹ ƪưů ƪƿŚſƹ ƆǀƈŴţ
ƹŮǀŰƇšŹƺƈŝƪůřźƯƶưƷŹŵšŚưǀưƈţƶƧƾţŹƺƇŹŵŶƃŚŝƾƯ
ŢſřƖƿŻƺţƹƂŴěƽŚƷƶƴƿżƷƱŶƃƪƣřŶůŦƗŚŝŵƺƃƭŚŬƳřƖƣƺưŝ ƱŚĭƹŚƳ ŢƿźƿŶƯ ƪƤƳƹ ƪưů ŦŰŝŹŵ ƽŶǀƬƧƹƮƸƯ ƪŗŚƀƯ Żř ƾƨƿ ƹƽŹƹōƖưūšŚƯŶųƶŗřŹřƽřźŝƵŵŚƠŤſřŵŹƺƯƲĮưƷŚƳƶǀƬƤƳƪƿŚſƹ
ƽŚƋŚƤţƹƶƋźƗŚŝƱŚƿźŤƄƯƹƱŚĭŶƴƃƹźƟƽřƶƗƺưŬƯƲǀŝƖƿŻƺţ ƮŤƀǀſźƿŶƯŶƃŚŞǀƯƶƟźƇƶŝƱƹźƤƯƹƽŵŚƈŤƣřƽřƶƳƺĮŝƆŴƄƯ ŵŹƺƯƶǀƬƤƳƪƿŚſƹŵřŶƘţƅƺƈųŹŵŶƿŚŝŚƸƴţƶƳƖƿŻƺţƹƽŹƹōƖưū ƱŚƿźŤƄƯƭřŶƧƶƧŶƴƧƆŴƄƯŶƿŚŝƶƨƬŝŵźǀĮŝƮǀưƈţƵŵŚƠŤſř ƪƣřŶů Śŝ ƾƫřƺţ ƹŶƳźǀĮŝ žƿƹźſŶƿŚŝ ƽř ƶǀƬƤƳ ƪƿŚſƹƶģ Ǝſƺţ ƶƧƾţLJƺƈŰƯŶƴƧƆŴƄƯżǀƳřŹƽŵƺūƺƯƹƪƤƳƹƪưůƶƴƿżƷ ƽŹƹōƖưūšLJƺƈŰƯƹƵŶƃƽźǀĭŹŚŝŹŚŞƳřŹŵŵƺƃƖƿŻƺţŢſřŹřźƣ ƆǀƈŴţŚŝšŚǀƬưƗƲƿřŶƳƺƃƾƯƵŶƳřŵźĭŻŚŝŹŚŞƳřƶŝřŵŶŬƯżǀƳƵŶƃ ŹŚŞƳřƦƿŻřźǀƀƯźƷŵƺƄǀƯƕƹźƃźǀƀƯƦƿƶŝƶǀƬƤƳƶƬǀſƹƦƿ ŶƿŚŝ źǀƀƯ źƷ ƽřźŝ ŵƺƃƾƯ ƮŤų Ʊō ƶŝ řŵŶŬƯ ƹ ŵƺƄǀƯ ƕƹźƃ ŵƺƃ ƲǀƯŚţ ƪưů ƪƿŚſƹ ŢǀƟźƓ ƹ ƽŹŚƧ ƱŚƯŻ ƽŚƷ ŢƿŵƹŶŰƯ ƎſƺţŶƿŚŝƽźŤƄƯźƷŶƃŚŞƳŻŚŬƯŚƋŚƤţƮǀƀƤţźĭřƲƿřźŝƵƹLjƗ ƾŝŚƿźǀƀƯ ƶƬŘƀƯ ƕƺƳ ƲƿŶƴģ ƱƺƴƧŚţ ŵźǀĮŝ žƿƹźſ ƶƬǀſƹ Ʀƿ ŶƳřƶŤƟźĭŹřźƣƾſŹźŝƹƶƘƫŚƐƯŵŹƺƯƕƺƋƺƯšŚǀŝŵřŹŵƶǀƬƤƳƪƿŚſƹ ŶƳŹřŵƵŹŚƃřƾţƹŚƠŤƯƽŵźŝŹŚƧƹƾƬưƗšLJŚůƶŝƪŗŚƀƯƲƿřƶģźĭř ƽřźŝ ƶǀƬƤƳ ƪƿŚſƹ źŧƺƯ ƹ řŹŚƧ ŢƿźƿŶƯ ƶƬŘƀƯźŝ ŚƸƳō ƾĮưƷ ƾƫƹ ƽŚƷƶƴƿżƷŶƴŤƀƷżƧźưŤƯƱŚƿźŤƄƯŻřƽřƶƗƺưŬƯƶŝƾƷŵžƿƹźſ
ƽźĭŹŚƧŵřŵźƸƯƹƽźƸĜſƽŶƸƯŶưŰƯƹƾƫƺƈŰƯŶƴģƾŰƐſŶƴģƾŝŚƿźǀƀƯƪŗŚƀƯŹŵžƿƹźſŶŞſƾŝŚƿƶƴǀƸŝêç
ƁƹŹ ŽŚſřźŝ ƦǀŤſŹƺǀƷ ƁƹŹ Ʀƿ >çè@ ŢƿřŹ ƹ ƥŹLjƧ 
ƶƀƿŚƤƯƢƿźƏŻřƁƹŹƲƿřŵźƨƬưƗŶƳřƵŵřŵƶƘſƺţƽŻŚſƵźǀųŷ Ţſř ƶŤƟźĭŹřźƣ ƾŝŚƿŻŹř ŵŹƺƯŶƿŶŰţ ƹ śŚƘƄƳř ƲǀŗŚě ƱřźƧ Śŝ ƶŤųŚƴƃ ƱƺŤſźǀƀƯ Ŷǀƫƺţ ƁƹŹ ƲƿźŤƸŝ ƱřƺƴƘŝ ƁƹŹ Ʋƿř
ŚŝƹƵŶƃƕƹźƃƶūƺƯźǀƛśřƺūƦƿŚŝƁƹŹƲƿřŢſřƵŶƃ
ŵŹřŵƶƴƿżƷƂƷŚƧŹŵƾƘſŚƷźǀƀƯŻřŚţƹŵźƷŜǀƧźţ
ŮƐſŹŚƸģƶŝřŹMDVRPƶƬŘƀƯ>çé@ŽřŶƫŚŝƹžƨǀūŶƷ 
ŢſřƱŚƿźŤƄƯƶŝŚƷŹŚŞƳřƆǀƈŴţƩƹřŮƐſŶƳŵƺưƳƶƿżŬţ Ʀƿ ƭƺſ ŮƐſ  Ţſř ŹŚŞƳř źƷ ƽřźŝ ƪŗŚƀƯ ƪů ƭƹŵ ŮƐſ
ƶƬŘƀƯƦƿźųōŮƐſƹŢſřƦƿŵƺƿźěšŹƺƈŝVRPƶƬŘƀƯ
ŢſřƶƴǀƸŝƽŚƷźǀƀƯŶǀƫƺţƽřźŝTSP
ƶŝřŹVRPƪŗŚƀƯƪůƽřźŝśƹŹŚūƮŤƿŹƺĮƫř>çê@źŞƬǀƯƹŢƬƿĥ 
ƶƬůźƯŵŹřŵƶƬůźƯƹŵƺĮƫřƲƿřŶƳŵřŵƶƘſƺţMDVRPƩŶƯ VRPƶƬŘƀƯŶƴģƭƹŵƶƬůźƯƹŚƷŹŚŞƳřƱŚƿźŤƄƯƆǀƈŴţƩƹř
śƹŹŚūƮŤƿŹƺĮƫřƎſƺţVRPƪŗŚƀƯŻřƭřŶƧźƷŢſřƵŵŚſ
ŶƳřƵŶƃƪů
ƮŤƿŹƺĮƫř Ʀưƨŝ řŹ MDVRP ƶƬŘƀƯ >çë@ Ʋǀģ ƹ ƲưƬǀţ 
ƶŝ ƱŚƿźŤƄƯ ƆǀƈŴţ Ʃƹř ƶƬůźƯ ŶƳŵźƧ ƾſŹźŝ saving
ƮŤƿŹƺĮƫř Ǝſƺţ ƵŵŚſ VRP ƪŗŚƀƯ ƪů ƭƹŵ ƶƬůźƯ ƹ ŚƷŹŚŞƳř
ŶƃŚŞǀƯŹŚŞƳřźƷƽřźŝsaving
ĨưĪŝ řŹ ƶǀƬƤƳ ƪƿŚſƹ ƾŝŚƿźǀƀƯ ƶƬŘƀƯ >çì@ƱřŹŚĪưƷƹ ƲǀƯ 
ŶƳŵřŵŹřźƣƾſŹźŝŵŹƺƯƾŞǀĩźţĨǀŤƳĥƮŤƿŹƺĮƫř
ƾŝŚƿźǀƀƯƶƿLJŶƴģƪŗŚƀƯƕƺƳƲƿźţƵŵŚſ>çí@ƾƟƺŝƹŚƀǀƯ 
ŵƺŝƶƿLJƹŵƽřŹřŵƱŚƄƿřƶƬŘƀƯŶƳŵřŵŹřźƣƾſŹźŝŵŹƺƯřŹ
ƽřźŝ(TS)ƕƺƴưƯƽƺŬŤƀūƁƹŹƦƿ>çî@ƱřŹŚƨưƷƹřŵŹƺƧ 
ƽřźŝ ƶƫŚƤƯ ƲƿřŹŵ ŶƳŵƺưƳ ƶŗřŹř MDVRP ƪŗŚƀƯ ƪů
ƵŵŚƠŤſřGENIƦǀŤſŹƺǀƷƁƹŹŻřƽźŤƄƯŵŶŬƯƽŹřŸĮƿŚū
ƪŗŚƀƯ ƪů ƁƹŹ Ʋƿźţ ƝƹźƘƯ ƁƹŹ Ʋƿř Ţſř ƵŶƃ
ŶƃŚŞǀƯMDVRP
ƪůƽřźŝƕƺƴưƯƽƺŬŤƀūƁƹŹƦƿ>èå@ƱřŹŚƨưƷƹŵŚƳŹ 
ƮŤƿŹƺĮƫř Ʀƿ ƶƫŚƤƯ ƲƿřŹŵ ŶƳŵƺưƳ ƶŗřŹř MDVRP ƪŗŚƀƯ
ŢſřƵŶƃƶŗřŹřƱŚĭŶƴƀƿƺƳƎſƺţPetal ƭŚƴŝƽŹŚƨŤŝř
ƪůƽřźŝƾŞǀƧźţƦǀŤƳĥƮŤƿŹƺĮƫřƦƿ>èæ@ƱřŹŚƨưƷƹƭŚǀƬƿƹ 
ƵŶƃƶŗřŹřƁƹŹƹŵƶƫŚƤƯƲƿřŹŵŶƳŵƺưƳƶŗřŹřMDVRPƪŗŚƀƯ śŚŴŤƳř ƾƟŵŚƈţ šŹƺƈŝ řŹ ƶǀƫƹř ŢǀƘưū Ʃƹř ƁƹŹ Ţſř ƾĮƿŚƀưƷ ƽƺŬŤƀū ŚŝřŹ ƶǀƫƹř ŢǀƘưū ƭƹŵ ƁƹŹ ƹ ŶƴƨǀƯ
Ʃƹř ƁƹŹ ƶŝ ŢŞƀƳ ƭƹŵ ƁƹŹ ƽŚƸŝřƺū ŶƴƨǀƯ ƲǀǀƘţ (NS)
ŢſřƶŤƃřŵŻŚǀƳƪůƽřźŝƽźŤưƧƱŚƯŻƹźŤƸŝ
ƮŤƿŹƺĮƫř Ʀưƨŝ řŹ MDVRP ƶƬŘƀƯ >èç@ ƱřŹŚƨưƷ ƹ ƥŚſ 
ƱŚƯŻŢƿŵƹŶŰƯƩŶƯƲƿřŹŵŶƳŵřŵŹřźƣƾſŹźŝŵŹƺƯƦǀŤƳĥ ƵŵŚſƱřƺƴƘŝTPSƶƬŘƀƯŵŹřŵŵƺūƹƽźŤƄƯƶŝLJŚƧƪƿƺŰţ
NP-HardƪŗŚƀƯŌżūMDVRPƹVRPƪŗŚƀƯŢƫŚůƲƿźţ ƮŤƀºǀſƽřźŝřŹƶƿLJŹŚƸģƩŶƯƲǀƫƹř>æé@ƱřŹŚƨưƷƹŢſźƯ 
ƾŝŚƿźǀƀºƯƶƬŘƀºƯŶºƳŵƺưƳƶŗřŹřšŚŬƳŚųŹŚƧšLJƺƈŰƯƖƿŻƺţ ŵŹƺºƯ>æê@ƽŶºǀƫƺƷƹƱŹƹƎſƺţƾƫƺƈŰƯŶƴģƶǀƬƤƳƪƿŚſƹ
ƽřźºŝƶºƿLJƶºſƩŶƯƦƿƽřŹřŵƶƫŚƤƯƲƿřŢƟźĭŹřźƣƾſŹźŝ
ŢſřƵŵƺưƳƶŗřŹřšŚŬƳŚųŹŚƧšLJƺƈŰƯƪƤƳƹƪưů
Ŷºƴģ ƶºǀƬƤƳ ƪƿŚſƹ ƾŝŚƿ źǀƀƯ ƶƬŘƀƯ >æë@ ƱřŹŚƨưƷ ƹ Ţƿƺƴŝ 
ƹŵřŶºƘţƩŶºƯƲºƿřŹŵ ŶºƳŵřŵŹřźºƣƪºǀƬŰţŵŹƺƯřŹƾƷŚĮŤƀƿř
ŢſřƵŶƃƉźƟŵƹŶŰƯƶǀƬƤƳƪƿŚſƹŢǀƟźƓ
Ŷƴģ ƶǀƬƤƳ ƪƿŚſƹ ƾŝŚƿźǀƀƯ ƩŶƯ Ʀƿ >æì@ ƮƿŚū ƹ ƺƠƫŵƹŹ 
ƾſŹźŝ řŹ ƽźŤƄƯ ƶŝ LJŚƧ ƪƿƺŰţ ƾƳŚƯŻ ƵŻŚŝ ƪƯŚƃ ƾƷŚĮŤƀƿř ƽŶƴŝ ƶƃƺų Ʃƹř ƶƬůźƯ ŵŹřŵ ƶƬůźƯ ƶſ ƶƫŚƤƯ Ʋƿř ŶƳŵźƧ
ƽŚƷźǀƀƯŵƺŞƸŝƭƺſƶƬůźƯƹƾŝŚƿźǀƀƯƭƹŵƶƬůźƯƱŚƿźŤƄƯ
ŶƃŚŞǀƯƵŶƃŶǀƫƺţ
ƽřźŝƾŞǀƧźţƦǀŤſŹƺǀƷƮŤƿŹƺĮƫřƦƿ>æí@ƽŹŚſƹƾŰƫŚƇ 
ƶŗřŹř ƾŰƐſ Ŷƴģ ƹ ƾƷŚĮŤƀƿř Ŷƴģ ƾŝŚƿźǀƀƯ ƪƿŚƀƯ ƪů ƆǀƈŴţƩƹřƶƬůźƯŢſřƶƬůźƯƶſƽřŹřŵƩŶƯƲƿřŶƳŵƺưƳ ƦƿźƷŹŵźǀƀƯŶǀƫƺţƭƹŵƶƬůźƯŹŚŞƳřƲƿźŤƨƿŵżƳƶŝƱŚƿźŤƄƯ
ŶƃŚŞǀƯƵŶƃŶǀƫƺţƽŚƷźǀƀƯŵƺŞƸŝƭƺſƶƬůźƯƹŚƷƶƃƺųŻř
ƦƿƹƕƺƴưƯƽƺŬŤƀūƮŤƿŹƺĮƫřƦƿ>æî@ƱřŹŚƨưƷƹƾůLjƟ 
ƾƫƺƈŰƯŶƴģƾŝŚƿźǀƀƯƪŗŚƀƯƽřźŝƾŞǀƧźţƦǀŤƳĥƮŤƿŹƺĮƫř
ƶǀƬƤƳƪƿŚſƹŢſřƩƺƈŰƯƶſƽřŹřŵƱŚƄƿřƩŶƯŶƳŵƺưƳƶŗřŹř ŵƺūƹ ƖƿŻƺţ ƵŚĮŤƀƿř Ʀƿ ƎƤƟ ƹ ƵŶƃ ƶŤƟźĭ źƔƳ Źŵ ƱŚƀƨƿ ƶǀƬƤƳ ƪƿŚſƹ ƾŝŚƿźǀƀƯ ƶƬŘƀƯ ƾƋŚƿŹ ƩŶƯ ƶƫŚƤƯ ƲƿřŹŵ ŵŹřŵ
ƶŗřŹřŮǀŰƇŵŶƗƾƐųƽżƿŹƶƯŚƳźŝšŹƺƈŝƩƺƈŰƯŶƴģƽřźŝ
ŢſřƵŶƃ
ƶƬŘƀƯ ƽřźŝ ƶƿLJ Ŷƴģ ƩŶƯ Ʀƿ >çå@ ƱřŹŚƨưƷ ƹ Śƴƿƺƫō 
ƶƿLJ ƶſ ƽřŹřŵ ƱŚƄƿř ƩŶƯ ŵƺưƳ ƶŗřŹř ƶǀƬƤƳ ƪƿŚſƹ ƾŝŚƿźǀƀƯ ƹŮǀŰƇŵŶƗƾƐųƽżƿŹƶƯŚƳźŝƩŶƯƦƿƶƫŚƤƯƲƿřŹŵŢſř ŵƺųƩŶƯ Źŵ ƱŚƄƿř Ţſř ƵŶƃƶŗřŹřƽŹŚƨŤŝř ƪůƁƹŹ Ʀƿ ŢſřƶŤƟźĭźƔƳŹŵšƹŚƠŤƯƶǀƬƤƳƶƬǀſƹŶƴģźǀƀƯźƷƽřźŝ ƾſŹźŝ ŢŝŚŧ ƽŚƋŚƤţ Śŝ ƾƫƺƈŰƯ Ĩƿ MDVRP ƩŶƯ ƲƿřŹŵ ŵřŶƘţ ƾƬŞƣ ŪƿŚŤƳ ƲƿźŤƸŝ Śŝ ƶƀƿŚƤƯŹŵ ƁƹŹ Ʋƿř Ţſř ƵŶƃ
Ƶŵřŵ ƂƷŚĩ řŹ ƵŶƃ ƾƏ ƽŚƷźǀƀƯ ƹ ŻŚǀƳ ŵŹƺƯ ƶǀƬƤƳ ƪƿŚſƹ
Ţſř
řŹ ƾƷŚĮŤƀƿř Ŷƴģ VRPTW ƶƬŘƀƯ >çæ@ ƱřŹŚƨưƷ ƹ Śſƺǀĭ 
ƦǀŤſŹƺǀƷƮŤƿŹƺĮƫřƂƃƶƫŚƤƯƲƿřŹŵŶƳŵřŵŹřźƣƾſŹźŝŵŹƺƯ
ŢſřƵŶƃƶƀƿŚƤƯƹƾůřźƏŚƷŹŚŞƳřƶŝƱŚƿźŤƄƯƆǀƈŴţƽřźŝ
ŢƫŚůŹŵ MDVRP ƶƬŘƀƯ >çç@ ƱřŹŚĪưƷ ƹ ŶǀƟƺŤƀƿźģ 
ƶƯŚƳźŝ ƩŶƯ Ʀƿ ƱŚƄƿř ŶƳŵřŵŹřźƣ ƾſŹźŝ ŵŹƺƯ řŹ Ʀƿŵƺƿźě ƽŻŚſŵřŻōƁƹŹƶŝřźƳōƹƵŵƺưƳƶŗřŹřƩŶƯƲƿřƽřźŝƾƐųƽżƿŹ
żǀƳ ƦǀŤſŹƺǀƷ ƁƹŹ Ʀƿ ƱŚƄƿř ŶƳŵƺưƳ ƪů ĦƳřźĭLJ ŜƿřźƋ ŵƺưƳƶŗřŹřƩŶƯƲƿřƪůƽřźŝ
êèƽźĭŹŚƧŵřŵźƸƯƹƽźƸĜſƽŶƸƯŶưŰƯƹƾƫƺƈŰƯŶƴģƾŰƐſŶƴģƾŝŚƿźǀƀƯƪŗŚƀƯŹŵžƿƹźſŶŞſƾŝŚƿƶƴǀƸŝ

ŻŚŬƯ ƵŵŚŤƟřŜƤƗ šŚƃŹŚƠſ Śƿ ƽŵƺūƺƯ ŵƺŞưƧ ŵŹřŵ ŵƺūƹ ƶǀƬƤƳ
źǀƜŤƯƹƲǀƘƯŮƐſźƷŹŵƽźŤƄƯźƷƽřźŝŵƺƿźěźƷƽŚƋŚƤţŢƀǀƳ
ŵƺƄǀƯƲǀƯŚţƶǀƬƤƳƶƬǀſƹƦƿŚŝƽźŤƄƯźƷƽŚƋŚƤţƪƧŢſř
ƲƿřƽŚƷŢƿŵƹŶŰƯƹƝŶƷƖŝŚţƽźǀĭƮǀưƈţƽŚƷźǀƜŤƯŚƷźŤƯřŹŚě ŵŵźĮǀƯŮƿźƄţźƿŻšŹƺƈŝŵƹŶŰƯŚƳƽżƿŹƶƯŚƳźŝƢƟřƦƿŹŵƩŶƯ
ƽźǀĭƮǀưƈţƽŚƷźǀƜŤƯƹŚƷźŤƯřŹŚěƞƿźƘţçæ
ŌřŶŞƯƵźĭƵŹŚưƃ I= 1,2, ,n
ŶƈƤƯƵźĭƵŹŚưƃ J= 1,2, ,m
ƶǀƬƤƳƶƬǀſƹƕƺƳ k= 1,2, ,k
źǀƀƯƵŹŚưƃ r = 1,2, ,R
ƶƿLJŮƐſƵŹŚưƃ L= 1,2, ,L
ƶƤƐƴƯƶǀůŚƳƵŹŚưƃ a= 1,2, ,A
ƩƺƈŰƯƵŹŚưƃ e= 1,2, ,E
ƺěŵƖǀưŬţƖƿŻƺţżĩźƯƵŹŚưƃ d= 1,2, ,D
aƶǀůŚƳƹL ŮƐſŹŵƱŚƿźŤƄƯŵřŶƘţ nLa
aƶǀůŚƳƹL ŮƐſŹŵ k ƶǀƬƤƳƪƿŚſƹŵřŶƘţ mkLa
aƶǀůŚƳƹL ŮƐſŹŵ kƶƬǀſƹƾưŬůŢǀƟźƓVkla
ƹ L ŮƐſ Źŵ e ƩƺƈŰƯŻř I ƽźŤƄƯŚƿ Ƶźĭ ƽŚƋŚƤţ diela
aƶǀůŚƳ
eƩƺƈŰƯŶůřƹƦƿƮŬůVe
ƾŤſřƺųŹŵ ƽLJŚƧ ƽŻŚſ ƵŵŚƯō ƹ ƽŹƹō Ɩưū ƭŚưţř ƱŚƯŻ tkLa
aƶǀůŚƳƹLŮƐſŹŵKƶƬǀſƹ
aƶǀůŚƳƹLŮƐſŹŵIƽźŤƄƯŹŚŝƶǀƬŴţƱŚƯŻšŶƯ tiLa
ƹ L ŮƐſ Źŵ J ƽźŤƄƯ ƶŝ I ƽźŤƄƯ Żř šźƟŚƀƯ ƱŚƯŻ tijLa
aƶǀůŚƳ
ŮƐſŹŵIƽźŤƄƯƶŝŢƬƸƯƁŹŚƠſƪƿƺŰţƱŚƯŻźŨƧřŶů M iLa
aƶǀůŚƳƹL ƹ L ŮƐſ Źŵ eƽLJŚĩƽřźŝ KƶƬǀſƹ ƾưŬů ŢǀƟźƓ Vekla
aƶǀůŚƳ
aƶǀůŚƳƹLŮƐſŹŵŹŚŞƳřƎſƺţeƽLJŚƧƶƋźƗƱřżǀƯ SeLa
ƶǀůŚƳƹLŮƐſŹŵKƶƬǀſƹŚŝIƽźŤƄƯƶŝƱŶǀſŹƱŚƯŻWikLa
a
ŹŵƶǀůŚƳŹŚŞƳřƽżƧźƯŹŚŞƳřŻřk ƶǀƬƤƳƶƬǀſƹŢƧźůƱŚƯŻU kla
aƶǀůŚƳƹLŮƐſ
aƶǀůŚƳƹLŮƐſŹŵJƵźĭƶŝIƵźĭŻřźǀƀƯƱƺưǀěƶƴƿżƷ Cijkla
kƶƬǀſƺŝ ƹLŮƐſŹŵJƵźĭƶŝ IƵźĭŻřkƶƬǀſƹƶƧƾţŹƺƇŹŵ X ijkla
ŢſřźƠƇšŹƺƈƴƿřźǀƛŹŵƹŢſřƦƿŶƿŚưƳŢĩźůaƶǀůŚƳ
ƵŵřŵƆǀƈŴţk ƶƬǀſƺŝaƶǀůŚƳƹLŮƐſŹŵIƽźŤƄƯźĭřYikla
ŢſřźƠƇšŹƺƈƴƿřźǀƛŹŵƹŢſřƦƿźŝřźŝƱōŹřŶƤƯŵƺƃ NP-żǀƳMDVRPƹVRPƪŗŚƀƯŽŚſřƲƿřźŝ>èè@Ţſř
ƽřźŝƵŶƃƶŗřŹřƪůƽŚƸƃƹŹŶƇŹŵ85ŻřƂǀŝŢſřHard ƦǀŤſŹƺǀƷŚŤƯŚƿƦǀŤſŹƺǀƷšŹƺƈŝ MDVRPƶƬŘƀƯ
ƽżƿŹ ƶƯŚƳźŝ ƩŶƯ Ʀƿ ƶŗřŹř ƲưƋ ƶƫŚƤƯ ƲƿřŹŵ èìŶƃŚŞǀƯ Ŷƴģ ƶǀƬƤƳ ƪƿŚſƹ ƾŝŚƿ źǀƀƯ ƪŗŚƀƯ ƽřźŝ ŮǀŰƇ ŵŶƗ ƾƐų ƪƣřŶů ƝŶƷ Śŝ ƾŰƐſ Ŷƴģ ó ƾƫƺƈŰƯ Ŷƴģ ƾƷŚĮŤƀƿř
ƲƿřƪůƽřźŝƦǀŤſŹƺǀƷƁƹŹƦƿƖƿŻƺţƽŚƷƶƴƿźƷƱŵƺưƳ
ŢſřƵŶƃƶŗřŹřƩŶƯ
ŚŤƯ ƁƹŹ Ĩƿ çååí ƩŚſ Źŵ >èé@ ƱřŹŚĪưƷ ƹ ƭŚǀƬƿƹ  ƪƿŚƀƯƪůƽřźŝĨǀŤƳĥƮŤƿŹƺĮƫřƽŚƴŞƯźŝƾŞǀĩźţĨǀŤſŹƺǀƷ
ŶƳŵƺưƳƶŗřŹřƖƿŻƺţżĩźƯŶƴģŚŝƾŝŚƿźǀƀƯ
ƽřźŝƾŞǀĩźţƁƹŹĨƿçååîƩŚſŹŵ>èê@ƱřŹŚĪưƷƹƺƠƫŵƹŹ 
ƶĩ ƖƿŻƺţ żĩźƯ Ŷƴģ Śŝ ƶǀƬƤƳ ƪƿŚſƹ ƾŝŚƿźǀƀƯ ƶƬŘƀƯ ŵƺŞƸŝ
ŶƳŵƺưƳƶŗřŹřŶƴŤƀƷīŹżŝŵŚƘŝřƹƾƳŚƯŻƵźŬƴěƽřŹřŵ
ƹŵĨǀŤſŹƺǀƷƁƹŹĨƿçåæåƩŚſŹŵ>èë@ƱřŹŚĪưƷƹƱřŹ 
ŢǀƟźƓƹƖƿŻƺţżĩźƯŶƴģŚŝƾŝŚƿźǀƀƯƪŗŚƀƯƽřźŝƽřƶƬůźƯ
ŶƳŵƺưƳƶŗřŹřŵƹŶŰƯ
ŢſřźƿŻŭźƄŝƶƯřŵřŹŵƶƫŚƤƯƲƿřŹŚŤųŚſ
ƾŝŚƿźǀƀƯƪƿŚƀƯŹŵžƿƹźſ ŶŞſƾŝŚƿƶƴǀƸŝƾƋŚƿŹƩŶƯřŶŤŝř ƪƣřŶů ƝŶƷ Śŝ ƾŰƐſ Ŷƴģ ó ƾƫƺƈŰƯ Ŷƴģ ó ƾƷŚĮŤƀƿř Ŷƴģ ƶƬŘƀƯ Ʋƿř žĜſ Ţſř ƵŶƃ ƶŗřŹř ƖƿŻƺţ ƽŚƷ ƶƴƿźƷ ƱŵƺưƳ
ƾƫƺƈŰƯ Ʀţ ƶƬŘƀƯ Ŷƴģ ƶŝ ƶƿżŬţ ƽŹŚƨŤŝř ƮŤƿŹƺĮƫř ŽŚſřźŝ ƶŝ ĦƳřźĭLJ ŜƿřźƋ ŽŚſřźŝ śŚǀưƧ ƖŝŚƴƯ ƆǀƈŴţ ŻřŶƘŝ ƹ ƪƿŶŞţ ƶŗřŹřƾƫƺƈŰƯƦţƾŝŚƿźǀƀƯƶƬŘƀƯƾƋŚƿŹƩŶƯƪŗŚƀƯŻřƦƿźƷ ƪů śřƺū ƽŚƌƟ ƶƘſƺţ ƽŹŚƨŤŝř ƮŤƿŹƺĮƫř ƽŚƴŞƯźŝ ƪŗŚƀƯ Ʋƿ řƹ ƖŝŚƴƯ ƹ ƵŵŚƠŤſř ŵŹƺƯ ƖŝŚƴƯ Ʋǀŝ ƶƀƿŚƤƯ Śŝ ŢƿŚƸƳŹŵ ŶƳř ƵŶƃ ŶƘŝ Ţſř ƵŶƃ ƭŚŬƳř ƖŝŚƴƯ ŮǀƐƀţ šŚǀƬưƗ ƵŶƃ Ƶŵřŵ ƆǀƈŴţ
Żř ƪƇŚů śřƺū Śŝ ƪƇŚů ƽŚƸŝřƺū  šŚǀƬưƗ Źřźƨţ ƶƬůźƯ Ŷƴģ ŢſřƶŤƟźĭŹřźƣŶǀŗŚţŵŹƺƯƱōƽźţźŝƹƶƀƿŚƤƯILPƽŚƸƃƹŹ
ƾƫƺƈŰƯŶƴģƶƬŘƀƯƾƋŚƿŹƩŶƯÏ
Źŵ žƿƹźſ ŶŞſ ƾŝŚƿ ƶƴǀƸŝ ƾƋŚƿŹ ƩŶƯ ŮƿźƄţ ƶŝ ƂŴŝ Ʋƿř Źŵ ƹ ƾƫƺƈŰƯ Ŷƴģó ƾƷŚĮŤƀƿř Ŷƴģ ƶǀƬƤƳ ƪƿŚſƹ ƾŝŚƿźǀƀƯ ƪƿŚƀƯ ƮƿŻřŵźěƾƯƖƿŻƺţƽŚƷƶƴƿżƷƱŵƺưƳƪƣřŶůƝŶƷŚŝƾŰƐſŶƴģ ŵƹŶŰƯ ŢǀƟźƓ Żř ƵŵŚƠŤſř Źŵ ƞƬŤŴƯ šLJƺƈŰƯ ƶƬŘƀƯ ƲƿřŹŵ ƶūƺţ Śŝ ŢƀƿŚŝ ƾƯ řŸƫ ŶƴƴƨǀƯ ŢŝŚƣŹ źĮƿŶƨƿ Śŝ ƶǀƬƤƳ ƪƿŚſƹ ŻřƦƿźƷŹŵƪƤƳƹƪưůƽŚƷƶŤſŵƶǀƬƤƳƪƿŚſƹŢǀƟźƓŢƿŵƹŶŰƯ ƾƯŚưţ ƽŚƋŚƤţ ƶƧ ŵŵźĭ ƲǀǀƘţ ƽř ƶƳƺĮŝ ŚƷźǀƀƯ ƹ ŭƺƐſ ƲƿřŹŵŵƺƃƲǀƯŚţŭƺƐſƶưƷŹŵƱŚƿźŤƄƯƶưƷƽřźŝšLJƺƈŰƯ
ŵŹƺƯƭLjƣřƖƿŻƺţżƧźƯƲƿřŵŹřŵŵƺūƹƾƬƇřƖƿŻƺţżƧźƯƦƿƩŶƯ ŶƘŝ ƶƬůźƯ Źŵ ŶƴƧƾƯ ƖƿŻƺţ ŚƸƳō Ʋǀŝ řŹ ƽř ƶƤƐƴƯ ƽŚƷŹŚŞƳř ŻŚǀƳ
ƖƿŻƺţ ŚƸƳō ƲǀŝřŹ ƱŚƿźŤƄƯ ŻŚǀƳŵŹƺƯ ƽŚƷLJŚƧ ƽř ƶƤƐƴƯ ƽŚƷŹŚŞƳř ƪƿŚſƹ ŢǀƟźƓ ŢƿŵƹŶŰƯ ƖƿŻƺţŮƐſ ƶƬůźƯ źƷ Źŵ ŶƴƴƧƾƯ
ƽźĭŹŚƧŵřŵźƸƯƹƽźƸĜſƽŶƸƯŶưŰƯƹƾƫƺƈŰƯŶƴģƾŰƐſŶƴģƾŝŚƿźǀƀƯƪŗŚƀƯŹŵžƿƹźſŶŞſƾŝŚƿƶƴǀƸŝêé
tkla t0jla wjkla (1X0jkla) . M ææ
k= 1,2,,K L=1,2,,L a=1,2,,A i=1,2,,n j=1,2,,m i  j

k1 is jNs æç
L1,2,…,L a1,2,…,A

X0,1
ijkla
i1,2,…,n j 1,2,…,m/ i j
æè
k 1,2,…,k a1,2,…,A L1,2,…,L
Wikla 0
1,2,…,ki 1,2,…,n
1,2,…,La 1,2,…,A æé
kXijkla 1for SN , | S |a 0S

ŹƺƔƴƯƶŝƝŶƷƖŝŚţźĮƳŚǀŝŹƺƔƴƯƶŝƝŶƷƖŝŚţźĮƳŚǀŝææƶƐŝřŹƾƬƇřƶƬŘƀƯƾƋŚƿŹƩŶƯŹŵƶƐŝřŹƾƬƇřƶƬŘƀƯƾƋŚƿŹƩŶƯŹŵ ŵƺƃŵƺƃƾƯŦƗŚŝƾƯŦƗŚŝççƶƐŝřŹƶƐŝřŹŶƃŚŝƾƯƖƿŻƺţƽŚƷƶƴƿżƷƱŵƺưƳƪƣřŶůŶƃŚŝƾƯƖƿŻƺţƽŚƷƶƴƿżƷƱŵƺưƳƪƣřŶů ƭŚŬƭŚŬƳřƶǀƬƤƳƶƬǀſƹƦƿƎſƺţƽźŤƄƯźƷƳřƶǀƬƤƳƶƬǀſƹƦƿƎſƺţƽźŤƄƯźƷƁŹŚƠſƁŹŚƠſŢſřƺųŹŵƶƧŢſřƺųŹŵƶƧ ŶƿŚŝ ƶǀƬƤƳ ƶƬǀſƹ źƷ ƶƧ Ţſř ƕƺƋƺƯ Ʋƿř źĮƳŚǀŝŶƿŚŝ ƶǀƬƤƳ ƶƬǀſƹ źƷ ƶƧ Ţſř ƕƺƋƺƯ Ʋƿř źĮƳŚǀŝm 1èè ƶƐŝřŹ ƶƐŝřŹ ŵƺƃŵƺƃ
éé ƶƐŝřŹ Źŵ ƶƐŝřŹ ŹŵX ŶƴƧ ƕƹźƃ ƶǀůŚƳ0ŶƴƧ ƕƹźƃ ƶǀůŚƳjkla  1 ƽżƧźƯ ŹŚŞƳř Żř řŹ ŵƺų źǀƀƯ ƽżƧźƯ ŹŚŞƳř Żř řŹ ŵƺų źǀƀƯ
ŹŚƨŝŵƹźǀƯŹŚƨŝƶǀůŚƳŹŚŞƳřj ƶǀůŚƳ1ŹŚŞƳř ƹ ƽżƧźƯƹƽżƧźƯŹŚŞƳřƽřźŝŹŚŞƳř ƽřźŝ å), å)(, (nn+1+1 źƠƇźƠƇžƿŶƳřžƿŶƳř
ƶŝŶƿŚŝřŹŵƺųźǀƀƯƶƬǀſƹźƷƶƧŵƺƃƾƯŦƗŚŝŹŚŞƳřƶŝŶƿŚŝřŹŵƺųźǀƀƯƶƬǀſƹźƷƶƧŵƺƃƾƯŦƗŚŝêƶƐŝřŹêŵƹźǀƯƶƐŝřŹ
ƎſƺţƶƤƬůŵŚŬƿřŦƗŚŝźƷ Ǝſƺţ ƶƤƬů ŵŚŬƿř ŦƗŚŝëƶƐŝřŹë ƶƐŝřŹŶƴƧƮŤųƶǀ ŶƴƧ ƮŤų ƶǀůŚƳůŚƳƽżƧźƯŹŚŞƳř ƽżƧźƯ ƱŶǀſŹƱŚƯŻƶƧŵƺƃƶŝƱŶǀſŹƱŚƯŻƶƧŵƺƃƾƯŦƗŚŝƾƯŦƗŚŝ ìƶƐŝřŹìƶƐŝřŹŵƺƃƾƯƶǀƬƤƳƶƬǀſƹźƷŵƺƃƾƯƶǀƬƤƳƶƬǀſƹ ƵƹLjƘŝƾƬŞƣƽźŤƄƯƶŝƱŶǀſŹƱŚƯŻŻřźţŵƹŻŶƿŚŞƳƽźŤƄƯźƷƶŝƱŚƯŻƵƹLjƘŝƾƬŞƣƽźŤƄƯƶŝƱŶǀſŹƱŚƯŻŻřźţŵƹŻŶƿŚŞƳƽźŤƄƯźƷ
ƶƐŝřŹíƶƐŝřŹŶƃŚŝƾƬŞƣƽźŤƄƯƶŝƱŶǀſŹŚţźǀƀƯƾƏƹŹŚŝƶǀƬŴţƱŚƯŻŶƃŚŝƾƬŞƣƽźŤƄƯƶŝƱŶǀſŹŚţźǀƀƯƾƏƹŹŚŝƶǀƬŴţ
ƪƿŶŞţ ƾƐų ƶƐŝřŹ ƦƿƵŵƺưƳ ƪƿŶŞţ ƾƐųƶƐŝřŹ Ʀƿƶŝ řŹƶŝ řŹì ƾƐų źǀƛ ƶƐŝřŹ Ɩƣřƹ Źŵì ƾƐų źǀƛƶƐŝřŹ Ɩƣřƹ ŹŵíƶƐŝřŹŦƗŚŝŵƺƃƾƯƵŵŚƠŤſřîƶƐŝřŹŵƺƃƾƯƵŵŚƠŤſříƶƐŝřŹŻřƎƤƟƩŶƯŹŵƹŢſřƵŵƺưƳíƶƐŝřŹŻřƎƤƟƩŶƯŹŵƹŢſř źŨƧřŶů Żř ŶƿŚŞƳ ƽźŤƄƯ źƷ ƶŝ ƱŶǀſŹ ƱŚƯŻ ŵƺƃ ƾƯ ŦƗŚŝƪƿƺŰţƱŚƯŻźŨƧřŶůŻřŶƿŚŞƳƽźŤƄƯźƷƶŝƱŶǀſŹƱŚƯŻŵƺƃƾîƯ ŢǀƟźƓŢƿŵƹŶŰƯřŹƶǀƬƤƳƶƬǀſƹŢǀƟźƓŢƿŵƹŶŰƯæåƶƐŝřŹŶƴƧŻƹŚŬţƽźŤƄƯƶŝƪƿƺŰţƱŚƯŻæåƶƐŝřŹŶƴƧŻƹŚŬţƽźŤƄƯƶŝ ƽŚƷŢſřƺųŹŵƮŬůƶƧƽřƶŤƟŚƿƆǀƈŴţƽŚƷŢſřƺųŹŵƮŬůƶƧƽřƶƳƺĭƶŝƶƳƺĭƶŝŶƴƧƾƯƞƿźƘţřŹƶǀƬƤƳƶƬǀſƹŶƴƧƾƯƞƿźƘţ
ŻƹŚŬţ Ʊō ŢǀƟźƓ Żř źǀƀƯ źƷ Źŵ ƶǀƬƤƳ ƶƬǀſƹ ƶŝ ƶŤƟææƶƐŝřŹŶƴĪƳŻƹŚŬţƱōŢǀƟźƓŻřźǀƀƯźƷŹŵƶǀƬƤƳƶƬǀſƹƶŝŚƿ ƆǀƈŴţ
ƽźŤƄƯƶŝLJŚĩƪƿƺŰţƱŚƯŻƶĩŵƺƃƾƯŦƗŚŝƭŚŬƳřƱŚƯŻŻřŶƿŚŞƳƽźŤƄƯƶŝLJŚĩƪƿƺŰţƱŚƯŻƶĩŵƺƃƾƯŦƗŚŝææƶƐŝřŹŶƴĪƳ ƵƹLjƘŝƱōŢſřƺųŹŵƽŻŚſƵŵŚƯōƹƽŹƹōƖưūƭŚŬƳřƱŚƯŻŻřŶƿŚŞƳƽřźŝ ƭŻLJ ƱŚƯŻ ƵƹLjƘŝ Ʊō ŢſřƺųŹŵ ƽŻŚſ ƵŵŚƯō ƹ ƽŹƹō Ɩưū ŹŵŢƿŵƹŶŰƯƲƿřŹŵŶƃŚŝƽźŤƄƯƶŝƶǀůŚƳŶƃŚŝƽźŤƄƯƶŝƶǀůŚƳƽżĩźƯŹŚŞƳřŻřƱŶǀſŹƽřźŝƭŻLJƱŚƯŻƽżĩźƯŹŚŞƳřŻřƱŶǀſŹ
ƶƐŝřŹtjla + tŶƃŚŝ ojla ƾƯźŝřźŝƪƣřŶůƹītjla + t ojla źŝřźŝƪƣřŶůƹīŹżŝŢŞŨƯŵŶƗĨƿŹżŝŢŞŨƯŵŶƗĨƿMŢƿŵƹŶŰƯƲƿřM ŹƺţŢƿŵƹŶŰƯźƿŻ ƶƤƬůŵƺƃƪǀĪƄţƾƯŹƺţźƿŻƶƤƬůƪǀĪƄţŻřƽźǀĭƺƬūŦƗŚŝŻř ƽźǀĭƺƬū ŦƗŚŝ æç ƶƐŝřŹ ŶƃŚŝƾƯæç
ŹŵƽźǀĭƮǀưƈţƽŚƷźǀƜŤƯŹŵŢƯLjƗŢƿŵƹŶŰƯźĮƳŚǀŝŢƯLjƗ ŢƿŵƹŶŰƯ źĮƳŚǀŝ æé ƹ æè ŢƿŵƹŶŰƯæé ŵƺƃƹƾƯæè
ŶƃŚŝƾƯƽźǀĭƮǀưƈţƽŚƷźǀƜŤƯŶƃŚŝƾƯ
ƶǀƬƤƳƪƿŚſƹŢƧźůƽŶƴŞƳŚƯŻŚŝƎŞţźƯƽŚƷŢƿŵƹŶŰƯƶǀƬƤƳƪƿŚſƹŢƧźůƽŶƴŞƳŚƯŻŚŝƎŞţźƯƽŚƷŢƿŵƹŶŰƯççèè
ŹŚŞƳřŹŚŞƳřƽżƧźƯŹŚŞƳřŻřŚƷšźƟƽżƧźƯŹŚŞƳřŻřŚƷšźƟŚƀƯƕƹźƃƽŶƴŞƳŚƯŻƶƯŚƳźŝƮǀƷřƺŴŝźĭřŚƀƯƕƹźƃƽŶƴŞƳŚƯŻƶƯŚƳźŝƮǀƷřƺŴŝźĭř ƶŤºƃřŵřŹƾůřƺºƳƹŭƺƐºſƶºưƷŹŵƶºǀƬƤƳƶƬǀºſƹźƷƎſƺţƶǀůŚƳƶŤººƃřŵřŹƾůřƺƳƹŭƺƐſƶưƷŹŵƶºººǀƬƤƳƶƬǀſƹźƷƎſƺţƶǀůŚƳ k ƶƬǀſƹŻřaƶǀůŚƳƹLŮƐſŹŵIƽźŤƄƯƶƧƾţŹƺƇŹŵ Ziekla ŢſřźƠƇšŹƺƈƴƿřźǀƛŹŵƹŢſřƦƿźŝřźŝŶƴƧŢƟŚƿŹŵřŹeƽLJŚƧ
ƾƬƇřƶƬŘƀƯƾƋŚƿŹƩŶƯçç
ƝŶƷƖŝŚţ
MIN Z  n m k L A C ijkla . X ijkla æ
I 1 J 1 k 1 l1 a 1
I  J
ƩŶƯƽŚƷŢƿŵƹŶŰƯ
nmLA
 . X ijkla 1ç
I  1j  1l  1a  1
I  J
I  J
k=1,2,,K L=1,2,,L A=1,2,,A
m 1
 X 0 jkla  1 è
j 1
K=1,2,,K L=1,2,,L A=1,2,,A
d0eladn1,ela, t0latn1, la ,t0,j,la ti,m1, laé
n1
 X i,0,k ,l ,a 1 ê
i1
K=1,2,,K L=1,2,,L A=1,2,,A
nm
 X ijkla   X ijkla  0 ë
i 1j 1 j  ij  i
Xijkla(wikla  tila tijla wjkla)  0 ìk= 1,2,,K L=1,2,,L a=1,2,,A
j=1,2,,m i  j

wikla tila tijla wjkla (1Xijkla).Mila í
n
w ikla  M ila  X ijklaî
 1
 i
k= 1,2, ,K L=1,2, ,L a=1,2, ,A j=1,2, ,m i  j
ne ne
V
i 1 e 1 d iela .e ii1j e 1 Z iekla   V kla æå

êêƽźĭŹŚƧŵřŵźƸƯƹƽźƸĜſƽŶƸƯŶưŰƯƹƾƫƺƈŰƯŶƴģƾŰƐſŶƴģƾŝŚƿźǀƀƯƪŗŚƀƯŹŵžƿƹźſŶŞſƾŝŚƿƶƴǀƸŝ
ƶºūřƺƯ ekla ĦºƳřźĭLJŜƿřźºƋŻřƶºƗƺưŬƯƦƿŚŝƱŚĭƹŵƶƬŘƀƯ ŹŵźºĮƿŵŢƿŵƹŶºŰƯŻřƭřŶƨĤǀƷŢƿŵƹŶŰƯƶŤſŵƲƿřŻřźǀƜŝŢſř
ŚºƷŢƿŵƹŶºŰƯźƿŚºſƲƿřźŝŚºƴŝŶƴƃŚŞǀưƳšLJƺƈŰƯƶưƷŚŝƍŚŞţŹř ŹřźºƣƪƤŤƀºƯƪŗŚƀºƯŵŚºŬƿřƽřźºŝƶºƿżŬţƪƯŚƗƱřƺƴƘŝŶƴƳřƺţƾưƳ ŢƿŵƹŶºŰƯŚºŝźƓŚºƴŤƯĦºƳřźĭLJŜƿřźƋƦưƨŝŽŚſřƲƿřźŝŶƳźǀĭ
ƦºƿƶƬŘƀƯnƶŝƾƫƺƈŰƯn ƾŝŚƿźǀƀƯƶƬŘƀƯƶǀƬƤƳƪƿŚſƹŢǀƟźƓ
ŵƺƄǀƯƪƿŶŞţƾƫƺƈŰƯ ƵŵŚºſƁƹŹLJƹřƶºƧŶƳŵřŵƱŚƄƳ>ç@ƱřŹŚĪưƷƹŹƺŝŚƧƶƐŝřŹƲƿřŹŵ ƪºưƗźºţƢºǀƣŵŚƸƿŻŚºſƵŵŚſźƿŚſƶŝŢŞƀƳĦƳřźĭLJŜƿřźƋƽŻŚſ ŢƿŵƹŶºŰƯƽŚºƴŞƯźŝĦƳřźĭLJŜƿřźƋƽŻŚſƵŵŚſƁƹŹŚǀƳŚŧŶƴƨǀƯ řŹƲǀŗŚºěŶºůƲƿźºţƽƺºƣŚƷŢƿŵƹŶŰƯźƿŚſŚŝƶƀƿŚƤƯŹŵŢǀƟźƓ ŻřƶƴǀƸŝƵŵŚƠŤſřƹƆǀƈŴţŚŨƫŚŧŶƷŶǀƯƶŗřŹřƶƴǀƸŝśřƺūƶŝŢŞƀƳ ƪƿŶºŞţŦºƗŚŝƽřƶƬůźƯŶƴģƽŻŚſƶƴǀƸŝƽŚƸƫŶƯŹŵśŚǀưƧƖŝŚƴƯ
ƪºƯŚƗźƔƳŻřƩŶƯƲƿřŹŵŶƃŶƷřƺųƪƤŤƀƯƶƬŘƀƯnƶŝƾƬƇřƩŶƯ
řźƿŻŢƀǀƳƶƴǀƸŝŚƯƹżƫƪƇŚůśřƺūƞƫř
æí
nEnE

Convex X : Min(i1 e1 d iela . .Ve )(i1 e1 Z iekla ) Vkla  
i j
nEnE
X : (i1 e1 d iela . .Ve )(i1 e 1 Z iekla )  Vkla 

i j

ŻřƪºƇŚůƪºůŻřźºţƽƺƣƾƫƺƈŰƯƦƿƶƬŘƀƯŻřƪƇŚůƪůƾƴƘƿ ƝŶºƷƖŝŚºţƲǀŗŚěŶůźĮƿŵšŹŚŞƗƶŝŢſřƾƐųƽŻŚſŵřŻōƁƹŹ ŶºůŚºŝƽƹŚƀºƯŚºƿźŤƨģƺºƧƾƫƺƈŰƯƦţƪŗŚƀƯŻřƦƿźƷŢƸū ƶºƿżŬţśƪºƯŚƗźºƔƳŻřŢºſřƾƬºƇřƶƬŘƀƯƝŶƷƖŝŚţƲǀŗŚě ƦºƿƶƬŘƀƯ(n)ŵŚŬƿřŦƗŚŝŵƹŶŰƯƖŝŚƴƯƆǀƈŴţƹƾƬƇřƶƬŘƀƯ
ƪŗŚƀºƯŻřƦºƿźºƷũƪºƯŚƗźºƔƳŻřŵƺƄºǀƯƪƤŤƀºƯƾƫƺƈŰƯ
ƶºƧƪºŞƣŢºƫŚůƶŝŢŞƀƳƱōƪůƶƧŢſřźǀƜŤƯmƽřŹřŵƪƤŤƀƯ ŢſřźţƱŚſōŜţřźưŝŵŹřŵŵƺūƹƽźǀĭƮǀưƈţźǀƜŤƯm.eƽřŹřŵ
ŹŵƵŶºƃƶºŗřŹřƎŝřƹŹƶŝƶūƺţŚŝƵƹŵƪůřźƯƶŝƍƺŝźƯšŚǀƬưƗ ŢſřƭŚŬƳřƪŝŚƣƾŤůřźŝźƿŻŢưƀƣ
ƾƫƺƈŰƯŶƴģƩŶƯƶƿżŬţƪůřźƯèæ
ƾŤººſřƺųŹŵšLJƺƈººŰƯƮººŬůŹřŶººƤƯƎººſƺŤƯƶ޺ºſŚŰƯæ
aƶǀůŚƳƹLŮƐſŹŵe ƽLJŚĩŻřƱŚƿźŤƄƯ
1 n
821094-42679

dela  d iela æînila i1
e=1,2,,E L=1,2,,L a=1,2,,A
ƮǀºƴƧƶƟŚºƋřƵŶºƃƶŗřŹřƩŶƯƶŝřŹźƿŻƽŚƷŢƿŵƹŶŰƯŶƿŚŝƮǀƃŚŝ ŵƺƄǀƯƩŶƯƾĭŶǀĤǀěƹƾţŚŞſŚŰƯŹŚŝƂƿřżƟřŦƗŚŝƪưƗƲƿř

n
Yikla Xijkla æê
i1
ji
I= 1,2,,n k= 1,2,,K L=1,2,,L a=1,2,,A

m
Ukla  X0 jkla. tkla æë
J1
I= 1,2,,n k= 1,2,,K L=1,2,,L a=1,2,,A
Y  0,1 æìikla
I=1,2,,n k=1,2,,K
L=1,2,,L a=1,2,…,A
šŹƺƇƶŝƶǀƬƤƳƪƿŚſƹŢĩźůƽŶƴŞƳŚƯŻŚŝƎŞţźƯƽŚƷŢƿŵƹŶŰƯ ƎƤƟƽźŤƄƯźƷƶĩŵƺƃƾƯŦƗŚŝæêƶƐŝřŹŶƳƺƃƾƯƞƿźƘţźƿŻ ƶŝ ƕƹźƃ ƱŚƯŻ æë ƶƐŝřŹ ŶŝŚƿ ƆǀƈŴţ ƶǀƬƤƳ ƶƬǀſƹ Ĩƿ ƶŝ ƵŵŚƯōƹƽŹƹōƖưūƭŚưţřƱŚƯŻźŝřźŝƪƣřŶůřŹƶǀƬƤƳƶƬǀſƹŢĩźů
ŢƯLjƗŢƿŵƹŶŰƯźĮƳŚǀŝæìƶƐŝřŹƹŶƷŵƾƯŹřźƣƁŹŚƠſƽŻŚſ
ŶƃŚŝƾƯƽźǀĭƮǀưƈţƽŚƷźǀƜƴƯŹŵ
ƾƫƺƈŰƯŶƴģƾƋŚƿŹƩŶƯƶƿżŬţè
ƽŚƷŹŚŤųŚſƽřŹřŵƾƫƺƈŰƯŶƴģƶƬŘƀƯƾƋŚƿŹƩŶƯƽŚƷŢƿŵƹŶŰƯ
ŵŵźĮǀƯŹƺŝżƯƩŶƯƱŶƃNp-HardŜŞſźƯřƲƿřŶƴŤƀƷšƹŚƠŤƯ ơƺƟŚƿƹƽŹŚƨŤŝřƽŚƸƃƹŹŻřŢƀƿŚŞǀƯƶƬŘƀƯƲƿřƪůŢƸūřŸƫƹ ƪůƽ řźŝ ƽŹŚƨŤŝřƽŚƸƃƹŹ Żř ƾƨƿ >èè@ŵƺưƳ ƵŵŚƠŤſřƽŹŚƨŤŝř ŻřƵŵŚƠŤſřƽřźŝŶƃŚŞǀƯƶƿżŬţƁƹŹƽŻŚſƶƴǀƸŝƵŶǀĤǀěƪŗŚƀƯ Śŝ ŢƿŵƹŶŰƯ ƶŤſŵ ƲƿŶƴģ ƽřŹřŵ ƶƧ ƾƬŗŚƀƯ Źŵ ƶƿżŬţ ƁƹŹ ƶƧŵŵźĮǀƯŭźƐƯƩřƺſƲƿřLJƺưƘƯŶƴŤƀƷšƹŚƠŤƯƽŚƷŹŚŤųŚſ ƶŤƟźĭźƔƳŹŵƶƿżŬţƪƯŚƗƱřƺƴƘŝŶƿŚŝŚƷŢƿŵƹŶŰƯŻřƶŤſŵƭřŶƧ
źƿŻƪƯřƺƗƲǀŝƶƧƽŵŚƌŤƯƎŝřƹŹŶƿŚŝƩřƺſƲƿřƶŝŲſŚěŹŵŵƺƃ
>æ@ŢƟźĭźƔƳŹŵřŹŶƃŚŞǀƯŹřźƣźŝ
ƵŶƃƶƿżŬţƪŗŚƀƯśřƺūŜǀƧźţŻřƪƇŚůŶůšŹŶƣ ƞƫř
ƾƗźƟƪŗŚƀƯƶŝƾƬƇřƶƬŘƀƯƶƿżŬţŢƫƺƸſ ś
ƾƗźƟƪŗŚƀƯŻřƦƿźƷƪůŢƫƺƸſ ũ
ƶƬŘƀƯƶŝƾŝŚǀŤſŵƽřźŝƾƗźƟƪŗŚƀƯśřƺūŜǀƧźţŢƫƺƸſ ŵ
ƾƬƇř
ƽřźŝ ƪůřźƯ Źřźƨţ ƹ ƵŶƳŚƯ ƾƣŚŝ ƖŝŚƴƯ ŮǀƐƀţ ŢƫƺƸſ Ƶ
śƺƬƐƯśřƺūƶŝƾŝŚǀŤſŵ
ŚºƸƴţƶºƧŵƺƄºǀƯƵŶƷŚƄºƯƾƫƺƈºŰƯŶºƴģƶƬŘƀƯƾƋŚƿŹƩŶƯŹŵ ƶºưƷŚºŝƍŚºŞţŹřŹŵ10ƶºƐŝřŹƶºǀƬƤƳƪƿŚºſƹŢǀƟźƓŢƿŵƹŶŰƯ
ŹŵŢƿŵƹŶºŰƯƶŤºſŵƲºƿřŚºŝźƓŚºƴŤƯƽŚƷźǀƜŤƯŢſřšLJƺƈŰƯ
ƽźĭŹŚƧŵřŵźƸƯƹƽźƸĜſƽŶƸƯŶưŰƯƹƾƫƺƈŰƯŶƴģƾŰƐſŶƴģƾŝŚƿźǀƀƯƪŗŚƀƯŹŵžƿƹźſŶŞſƾŝŚƿƶƴǀƸŝêë
ƾƫƺƈŰƯƦƿƾƋŚƿŹƩŶƯé
ƶŝƾƫƺƈŰƯnƾƋŚƿŹƩŶƯƶƿżŬţƹŵƹŶŰƯƖŝŚƴƯƆǀƈŴţŻřžě ƪƿŚſƹƾŝŚƿźǀƀƯƶƬŘƀƯƾƋŚƿŹƩŶƯƾƫƺƈŰƯƦţƾƋŚƿŹƩŶƯn źƿŻ šŹƺƈŝ ƾƫƺƈŰƯ Ʀƿ ƹ ƾŰƐſ Ŷƴģ ƾƷŚĮŤƀƿř Ŷƴģ ƶǀƬƤƳ ƹ ƝŶƷ ƖŝŚţ ƽźǀĭƮǀưƈţ ƽŚƷźǀƜŤƯ ŚƷźŤƯřŹŚě ŵƺŝ ŶƷřƺų
ƾƫƺƈŰƯŶƴģƩŶƯŚŝƶƀƿŚƤƯŹŵƾƫƺƈŰƯƦţƩŶƯƽŚƷŢƿŵƹŶŰƯ ŶƴƧƾƯźǀǀƜţæƩƹŶūšŹƺƈŝ šLJƺƈŰƯŻřƦƿźƷŻŚǀƳŵŹƺƯŢǀƟźƓŢŞƀƳƶŞſŚŰƯ ç
ela e
ela
v
d
.

e

ela

v

d

.

Eçå
 d ela .ve
e1
e= 1,2,,E L=1,2,,L a=1,2,,A

RƶƬǀſƹŹŵšLJƺƈŰƯŻřƦƿźƷŻŚǀƳŵŹƺƯŢǀƟźƓƶŞſŚŰƯè
aƶǀůŚƳƹLŮƐſƽřźŝ
Vekla ela .Vkla çæ
e= 1,2,,E L=1,2,,L a=1,2,,A
ƾƫƺƈŰƯŶƴūƹƾƫƺƈŰƯĨţƩŶƯƶƀƿŚƤƯæƩƹŶū
ƾƫƺƈŰƯŶƴģƩŶƯ ƾƫƺƈŰƯƦţƩŶƯ
aƶǀůŚƳƹLŮƐſƽřźŝe ƽLJŚĩƽřźŝiƽźŤƄƯƽŚƋŚƤţ diela aƶǀůŚƳƹLŮƐſŹŵiƽźŤƄƯƽŚƋŚƤţ dila
ƽLJŚĩkƹŹŵƺųŻřaƶǀůŚƳƹLŮƐſŹŵiƽźŤƄƯƶƧƾţŹƺƇŹŵ Ziekla
ŢſřźƠƇšŹƺƈƴƿřźǀƛŹŵƹƦƿŶƴƧŢƟŚƿŹŵe LJŚƧkƹŹŵƺųŻřaƶǀůŚƳƹLŮƐſŹŵIƽźŤƄƯƶƧƾţŹƺƇŹŵ Zikla
ŢſřźƠƇšŹƺƈƴƿřźǀƛŹŵŢſřƦƿŶƴƧŢƟŚƿŹŵ
aƶǀůŚƳƹLŮƐſŹŵkƶƬǀſƹƾưŬůŢǀƟźƓVkla ƹL ŮƐſŹŵe ƽLJŚĩƽřźŝk ƶƬǀſƹƾưŬůŢǀƟźƓVekla aƶǀůŚƳ

n E d ilea .V e n E Z ikela   V kla
 i 1 e 1 i1 e 1  
n d ila .V e  n Z ikla   V ekla
 i 1  i 1
aƶǀůŚƳƹLŮƐſ Źŵe ƩƺƈŰƯŻŚǀƳŵŹƺƯŢǀƟźƓŢŞƀƳela Vekla ela .Vkla
ƹƶƴƿżƷƪƣřŶůŚŝƱŚƿźūźŨƧřŶůƁƹŹƶƬưūŻřƝƹźƔƯƽŚƷƶƨŞƃ >æ@ŢſřƪůƪŝŚƣƞƸƃźƧšLJŵŚƘƯ
ƦƿƹźƠƇƽŚƷźǀƜŤƯŢǀƘƋƹƲǀǀƘţêæ
šŚƃŹŚƠſƽŵƺūƺƯ ŵƺŞưƧ ƶƘƫŚƐƯ ŵŹƺƯ ƩŶƯ Źŵ ƶƨƴƿř ƶŝ ƶūƺţ Śŝ ŢƀƿŚŝƾƯźǀƀƯźƷŹŵƶǀƬƤƳƪƿŚſƹƾƯŚưţŢƀǀƳŻŚŬƯƵŵŚŤƟřŜƤƗ
śřƺūŚţŶƃŚŝƶŤƃřŵŢǀƟźƓƩƹřƽźŤƄƯƽŚƋŚƤţƱřżǀƯƶŝƪƣřŶů ƾƴƘƿŵƺƃƪƇŚůƲƨưƯ
Vekla dila 
çè
(Zikla Xoikla Yikla 1
I= 1,2,,n k= 1,2,,K L=1,2,,La=1,2,,A
ƮƷźĮƿŵƱŚƿźŤƄƯƽřźŝŚƷźǀƀƯŻřƾƌƘŝŹŵƩƹřƽźŤƄƯźŝƵƹLjƗ ƶƨǀţŹƺƇŹŵŵŵźĭƪƇŚůƲƨưƯśřƺūŚţƶŤƃřŵŵƺūƹŢǀƟźƓŶƿŚŝ ŢǀƘƋƹ ƱŶƃ ƲƃƹŹ ƶŝ ƾƳŚƿŚƃ ƦưƧ ŵƺƃ ƆŴƄƯ ƕƺƋƺƯ Ʋƿř
ƪŝŚƣ ƂƷŚƧ Ʊō ƖŞţ ƶŝ ŵƺưƳ ŶƷřƺų Zikla ƽŚƷźǀƜŤƯ Żř ƾƌƘŝ ŶƿŶŰţ ƹ śŚƘƄƳř ƮŤƿŹƺĮƫř šŚŞſŚŰƯ ƮŬů Źŵ ƽř ƶƔůLjƯ ŢſřƭŻLJřŶŤŝřƕƺƋƺƯƲƿřƶŝƾſźŤſŵƽřźŝŶƷŶǀƯűŹƽŵŚƸƴƄǀě
řŹ(i+1)ƽźŤƄƯƶŝIƽźŤƄƯŻřVekla (i)ƾƫŚſŹřŢǀƟźƓƪƣřŶů ŵŹƹōŢſŶŝ
ƦţƾŝŚƿźǀƀƯƪŗŚƀƯŻřƦƿźƷƪůƾƋŚƿŹƁƹŹê ƾƫƺƈŰƯ
ƩŶƯƪůƽřźŝŶƿŶŰţƹśŚƘƄƳřƁƹŹƦƿƶŗřŹřƝŶƷƶƨƴƿřƶŝźƔƳ ƶƧƮǀŗŚưƳƪưƗƽřƶƳƺĮŝŢƀƿŚŝƾƯŶƃŚŞǀƯƾƫƺƈŰƯƦţƾƋŚƿŹ źƔƳŻřƦƿƹźƠƇƽŚƷźǀƜŤƯŻřƾƨƿŢǀƘƋƹŹřźƨţƶƬůźƯźƷŹŵ řŹƾƳŚǀƯŢǀƘƋƹƦƿźĭřŢƫŚůƲƿřŹŵŵƺƃƲƃƹŹƱŵƺŝƦƿƹźƠƇ źĮƿŵƽŵřŶƘţƶŤƃřŵƦƿŹřŶƤƯŚƷźǀƜŤƯŻřƽŵřŶƘţƮƿźǀĮŝźƔƳŹŵ ƽřźŝ ŹƺƔƴƯ ƲƿŶŝ ŶƴŤƀƷ ŵřŻō ƾƤŝŚƯ ƹ ƶŤƟźĭ ŵƺŴŝ źƠƇ ŹřŶƤƯ
šŹƺƈŝ řŹ Zikla, Xijkla, Yikla  ƩŶƯ Ʀƿ ƹźƠƇ ƽŚƷźǀƜŤƯ ƮǀƴƧƾƯƉźƟƦƿƹźƠƇƲǀŝƶŤſƺǀěƽŚƷźǀƜŤƯ
0  (Zikla , X ijkla, Yikla ) 1çç
ƶƘſƺţ ƾƫƺƈŰƯ Ʀţ ƾƋŚƿŹ ƩŶƯ śřƺū ƽŚƌƟ ƪưƗ Ʋƿř źŧř Źŵ ƽřźŝƲǀŗŚěŶůƦƿƱřƺƴƘŝƶƬŘƀƯƲƿřŻřƪƇŚůśřƺūřŸƫƹŶŝŚƿƾƯ
ƽŚƷźǀƜŤƯ Żř ƦƿźƷ ƽřźŝ šŹƺƇ ƲƿřŹŵ ŵƹźǀƯ ŹŚƨŝ ƾƬƇř ƶƬŘƀƯ ƶŤƟźĭ šŹƺƇ ƽŻŚſŵřŻō ƪưƗ Ʀƿ ƾƫƺƈŰƯ Ʀţ ƩŶƯ Ʀƿƹ źƠƇ ƶƬŘƀƯƦƿƹźƠƇƽŚƷźǀƜŤƯƽŻŚſŵřŻōšŚǀƬưƗƭŚŬƳřŻřŶƘŝŢſř ƪƿŶŞţ ƾƐų ƶƴƿżƷ Śŝ ƶƨŞƃ ƩŶƯ Ʀƿ ƶŝ ƾƫƺƈŰƯ Ʀţ ƾŝŚƿźǀƀƯ
ƪŗŚƀƯ ƪů ƩƹřŶŤƯ ƽŚƸƃƹŹ Żř ƾƨƿ Śŝ ƾƐų ƩŶƯ Ʋƿř ŵƺƄǀƯ
êìƽźĭŹŚƧŵřŵźƸƯƹƽźƸĜſƽŶƸƯŶưŰƯƹƾƫƺƈŰƯŶƴģƾŰƐſŶƴģƾŝŚƿźǀƀƯƪŗŚƀƯŹŵžƿƹźſŶŞſƾŝŚƿƶƴǀƸŝ
ƲƿřźŝŚƴŝƮǀƴƧƶŞſŚŰƯřŹV Aekla(i1)ŶƿŚŝ
Vekla(i1)  min di1 ,la .Ve ,Vekla(i) èå
ŶºƷřƺųV A ekla (i) Śºƿ d i 1 ,la .V e źŝřźŝơƺƟƶƐŝřŹƪƣřŶů
Źřźºƣźŝ V A ekla (i 1) V Aekla (i) ƶƐŝřŹƵŹřƺưƷƲǀƴĤưƷŵƺŝ ŚºţƱŚƿźŤƄºƯƽŚºƋŚƤţƕƺºưŬƯƶºƨƴƿřƶŝƮƬƗŚŝźĮƿŵƝźƏŻřŢſř
ŢºŝŚŧƶǀƌºƣŢºſřŹřźºƣźŝƶƐŝřŹƹŶƃŚŞǀƯƆŴƄƯ(i-1)ƽźŤƄƯ
Ʊŵƺ ŝƦºƿƹźƠºƇŢǀƘ ƋƹƲǀºǀƘţƽřźºŝƶǀƌ ƣƲºƿřŢºſřƵŶºƃ
ŢſřƵŶƃƵŵŚƠŤſř Zikla ƽŚƷźǀƜŤƯ
 Fi1 ,kla  Fi , kla  d ila .Ve  Vekla (i) èæ
ŶƿŶŰţƹśŚƘƄƳřƮŤƿŹƺĮƫř êè
ƹèçƎŝřƹŹƶŝƶūƺţŚŝřŹƩƺŞƣƪŝŚƣƶǀƫƹřśřƺūŵƺūƹæƭŶƣ
ŶǀƴƧƾſŹźŝèè
qkla  max (V1kla ,V2 kla ,…..Vekla ) èç
n
V Aekla (i)  qekla n èè
i1
ƹŢſřƪŝŚƣśřƺūƽřŹřŵƶƬŘƀƯƵŚĮƳōŵƺƃŌŚƋŹřèèƶƐŝřŹźĭř
ƞƣƺŤƯƹŵŹřŶƳƩƺŞƣƪŝŚƣśřƺūƶƬŘƀƯŵƺƄƳŌŚƋŹřèèƶƐŝřŹźĭř
řŹ Ĩƿƹ źƠƇ ƽŚƷźǀƜŤƯ ŢǀƘƋƹêæ ƂŴŝ ƽƺĮƫř Śŝ ŶƿƺƃƾƯ
ŶǀƴĩƲǀǀƘţ ƶŝ řŹ ƾƫƺƈŰƯ Ʀţ ƾŝŚƿźǀƀƯ ƶƬŘƀƯ ƶŤƟŚƿ ƶƘſƺţ ƩŶƯ ç ƭŶƣ
ŵŹƺƯŢǀƟźƓƱřżǀƯšŹƺƈƴƿřŹŵŶǀƴƧƪů(Out of Kilter) ƁƹŹ
a ƶǀůŚƳ ƹ L ŮƐſŹŵ ƹ źǀƀƯ źƷ Źŵ ƶǀƬƤƳ ƪƿŚſƹ Żř ƦƿźƷ ŻŚǀƳ
ŵƺƄǀƯƶŞſŚŰƯ
ŶǀƴƧƲǀǀƘţřŹƦƿƹźƠƇƽŚƷźǀƜŤƯŢǀƘƋƹèƭŶƣ
ƽŵřŻōźǀƜŤƯĢǀƷ X ijkla ƽŚƷźǀƜŤƯƲǀŝƶƧƾţŹƺƇŹŵ éƭŶƣ
Ʋǀŝ Żř šŹƺƈƴƿřźǀƛŹŵ ŶƿƺƃƾƯ ƞƣƺŤƯ ŶƃŚŝ ƶŤƃřŶƳ ŵƺūƹ
ƝŶƷƖŝŚţŹŵƶƴƿżƷŵƺŞƸŝƲƿźŤƄǀŝƶƧƽźǀƜŤƯƱōŵřŻōƽŚƷźǀƜŤƯ
ƮǀƷŶǀƯƭŚŬƳřřŹśŚƘƄƳřšŚǀƬưƗƹśŚŴŤƳřŵŹřŵřŹ i , kla  maxCijkla.X ijkla /i  jèé
i= 1,2,,n j=1,2,,m
ŢǀƘºƋƹ(n)ƽźŤƄºƯŚţ(i)ƽźŤƄƯŻřźǀƀƯƦƿŹŵźĭřêƭŶƣ ŚºƿƹŶºƃŚŝŹřźƣźŝźƿŻƍźƃƹƵŶƃƲǀǀƘţƦƿƹźƠƇƽŚƷźǀƜŤƯƶưƷ
ƭŶºƣƶŝšŹƺƈƴƿřźǀƛŹŵŶǀƴƧƞƣƺţŵƺƄƳƪƇŚůśřƺūŹŵƽŵƺŞƸŝ Ŷƿŵźĭźŝƭƺſ
m
 Z ijkla . d iLa .V e  V eklaèê
J 1
K= 1,2,,k L=1,2,,L a=1,2,,A

qekla  MinVe1la , Ve2la , ….,Vekla çé
V Lekla(i)  Mindi1,la .ve Vekla(i 1),qk  if i  n
0if i  n
ƶǀůŚƳƹLŮƐſŹŵIæƽźŤƄƯƽřźŝƶƧƮǀƷŵƆǀŴƄţƶƨƳōƽřźŝ (i) ŶƿŚŝ řŶŤŝř źǀų Śƿ ŵƺƃ ƶŤƟźĭ źƔƳ Źŵ ŶƿŶū ƶƬǀſƹ ŶƿŚŝ a
Źŵ ƱƺǀƯŚƧ Śƿō ƾƴƘƿ ŵƺƃ ƶŞſŚŰƯ ƱŚƿźŤƄƯ ƶưƷ ƽřźŝ V Aekla
ƵźĭƶŝƹŶƷŵƾƯƶƯřŵřźǀƀƯƶŝƶƨƴƿřŚƿŵŵźĭƾƯźŝƺěŵƶŝI Ƶźĭ
ƆǀƈŴţŶƿŶūƲǀƃŚƯƹƮƿŹřŵŹřźƣƺěŵƩƹřŹŵƶƳźĭƹŵƹŹƾƯi+1
ŶŝŚŝƾƯ
ir
dla . ve dila.Ve  qekla if i  n
i1
V Aekla(i)  dila . veif inçê

ir dla . ve dila.Ve qekla
i1
ƹLŮƐſŹŵIƽźŤƄƯŻřŶƳřƺţƾƯƶƧƾƳŚƿźūƮŬůźŨƧřŶůžĜſ ƮǀƴƧƶŞſŚŰƯřŹŶƴƧŹƺŞƗKƶƬǀſƹƎſƺţaƶǀůŚƳ
çë
Vuekla(i)qeklai1 dila .ve di1 , La .Ve ZiklaXijklaYijkla1
i1
qeklai1 dila .ve di1 , La .Ve ZiklaXijklaYijkla0
i1
źǀƀƯźƷŹŵƦƿƹźƠƇƽŚƷźǀƜŤƯƍŚŞţŹřêç
LŮƐſƽřźŝźǀƀƯźƷŹŵƦƿƹźƠƇƽŚƷźǀƜŤƯƍŚŞţŹřƲǀǀƘţƽřźŝ ƶǀƌƣ Ţſř ƵŶƃ ƵŵŚƠŤſř źƿŻ ƶǀƌƣ Żř k źǀƀƯ ƹ A ƶǀůŚƳ ƹ kƶƬǀſƹŚŝaƶǀůŚƳƹLŮƐſŹŵ Zikla 1 ƍźƃŚŝƶƧƾţŹƺƇŹŵ
ƶǀƬƤƳ ƶƬǀſƹ ƽŶƘŝ ƱŚƿźŤƄƯ ƽřźŝ ŵƺƃ ƪƇŚů ƩƺŞƣ ƪŝŚƣ śřƺū
ŵƺƃƆǀƈŴţŶƿŶū
IF Zikla 1  (Zi1, kla Zi2, kla …..Znkla1)çì OR IF
dila  0  (di1, la di2, la …..dnla)  0
ŶƃŚŝŹřźƣźŝƶƬŘƀƯƕƹźƃŹŵ Zikla 1 ƍźƃŶǀƴƧƉźƟšŚŞŧř ŢƃřŵƮǀƷřƺųšŹƺƇƲƿřŹŵ
Fikla  d ila .V e  V ekla (i) çí
ƽŚƷźǀƜŤƯŢǀƘƋƹƱŶƃƲƃƹŹƽřźŝ
(Zi1, klaϭ Zi2, klaϭ…..ϭZ nkla ) çî
ƽźĭŹŚƧŵřŵźƸƯƹƽźƸĜſƽŶƸƯŶưŰƯƹƾƫƺƈŰƯŶƴģƾŰƐſŶƴģƾŝŚƿźǀƀƯƪŗŚƀƯŹŵžƿƹźſŶŞſƾŝŚƿƶƴǀƸŝêí
ƪƧ ƽřźŝèí ƶƐŝřŹ ĨưĪŝ řŹ ƖŝŚƴƯ ŮǀƐƀţ šŚǀƬưƗ é ƭŶƣ
ƭŚŬƳřaƶǀůŚƳƹLŮƐſkƶƬǀſƹŹŵ(RCT)ƵŶƳŚưǀƣŚŝŢǀƟźƓ ŶǀƷŵ ƞƣƺţ ƍźƃ ƶŝ ƱŶǀſŹ ƱŚƯŻ Śţƹ Ŷƿŵźĭźŝ ƭƹŵ ƭŶƣ ƶŝ ê ƭŶƣ
ƮŤƿŹƺĮƫř ƞƬŤŴƯ ƪůřźƯ Źŵ ƞƣƺţ Ǝƿřźƃ ŶǀƷŵ ƶƯřŵř řŹ ƶƬŘƀƯ ŢſřƵŶƃƱŚǀŝêèŢưƀƣŹŵŶƿŶŰţśŚƘƄƳř
ƽŵŚƸƴƄǀěƮŤƿŹƺĮƫřŹŚŞŤƗřë
ŵřŶƘţ ƵŶƃ ƶŗřŹř ƽŵŚƸƴƄǀě ƮŤƿŹƺĮƫř ƾƿōŹŚƧ ƱřżǀƯ ƾſŹźŝ ŢƸū
ŶƳřƵŶƃŵŚŬƿřźƿŻšŚƈŴƄƯŚŝƾƟŵŚƈţƶƬŘƀƯŵŶƗèåå
ŵƹŶŰƯŹŵƵŶƃŵŚŬƿřƪƿŚƀƯŵŚƘŝřæ
(N.E.L.D.K) =(åå æê ê çå èƾƫř(N.E.L.D.K) = (í ê ç ê æ
ŢſřƵŶƯōçƩƹŶūŹŵƪŗŚƀƯŢƀǀƫŢſř
źƷŹŵƾƳŚǀƯƽŚƷŹŚŞƳřŻřƦƿźƷƽřźŝƽźǀĭŹŚŝƹƽŻřŶƳřŹŚŝƱŚƯŻç
íå Ţųřƺƴƨƿ ƖƿŻƺţŻř ƶƳŚĭřŶū ƹ ƾƟŵŚƈţ šŹƺƈŝ ƶǀůŚƳƹ ŮƐſ
ŶƳřƵŶƃśŚŴŤƳřƶƤǀƣŵèå
ƹŭƺƐſƶưƷŹŵƽźŤƄƯŚƿŹŚŞƳřƹŵźƷƲǀŝźƷźǀƀƯƾƏƱŚƯŻè
ƶƤǀƣŵæååæååå Ţųřƺƴƨƿ ƖƿŻƺţ Żř ƶƳŚĭřŶū šŹƺƈŝ ƾůřƺƳ
ŶƳřƵŶƃśŚŴŤƳř ƖƿŻƺţŻřƶƳŚĭřŶūƹƾƟŵŚƈţšŹƺƈŝšLJƺƈŰƯŻřƦƿźƷƮŬůé
śŚŴŤƳřŜƘĪƯźŤưǀŤƳŚſæå æå æåæåå æåå æååŢųřƺƴƨƿ
ŶƳřƵŶƃ ƖƿŻƺţŻřƶƳŚĭřŶūƹƾƟŵŚƈţšŹƺƈŝƶǀƬƤƳƪƿŚſƹŻřƦƿźƷƮŬůê
ŜƘĪƯ źŤưǀŤƳŚſ æêå æåå æååêåå çåå çåå Ţųřƺƴƨƿ
ŶƳřƵŶƃśŚŴŤƳř
šŹƺƈŝ šLJƺƈŰƯ Żř ƦƿźƷ ƽřźŝ ƾƳŚǀƯ ƽŚƷŹŚŞƳř ƽŚƋŚƤţë
ŶƳřƵŶƃśŚŴŤƳřçååæåååŢųřƺƴƨƿƖƿŻƺţŻřƾƟŵŚƈţ
ƾƟŵŚƈºţšŹƺƈºŝšLJƺƈŰƯŻřƦƿźƷƽřźŝƱŚƿźŤƄƯƽŚƋŚƤţì
ŶƳřƵŶƃśŚŴŤƳřæåêåŢųřƺƴƨƿƖƿŻƺţŻř ƶºǀůŚƳƹŮƐºſźƷŹŵƱŚƿźŤƄƯŻřƦƿźƷƽřźŝƽŻřŶƳřŹŚŝƱŚƯŻí
ƶºƤǀƣŵçåèåŢºųřƺƴƨƿƖºƿŻƺţŻřƶƳŚĭřŶūƹƾƟŵŚƈţšŹƺƈŝ
ŶƳřƵŶƃśŚŴŤƳř
ƵŶƃ ƶŤƃƺƳ Matlab ƎǀŰƯ Źŵ



قیمت: تومان


دیدگاهتان را بنویسید