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

1268732040128Downloaded from ijiepm.iust.ac.ir at 16:53 IRST on Saturday November 4th 2017

Downloaded from ijiepm.iust.ac.ir at 16:53 IRST on Saturday November 4th 2017

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ƺƈŰƯ
1268732040128Downloaded from ijiepm.iust.ac.ir at 16:53 IRST on Saturday November 4th 2017

Downloaded from ijiepm.iust.ac.ir at 16:53 IRST on Saturday November 4th 2017

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

ƱřƺŤǀƯƾƬƧŹƺƐŝřŹƶǀƬƤƳƪƿŚſƹƾŝŚƿźǀƀƯŹŵƾŤƿźƿŶƯšŚưǀưƈţ ƵŚºţƺƧƹšŶƯƱŚǀƯšŶƯŶƴƬŝƽźǀĭƮǀưƈţƪŗŚƀƯƶŤſŵƶſŹŵ źŤƄǀŝŶǀƧŚţLJƺưƘƯšŶƯŶƴƬŝƪŗŚƀƯŹŵŵƺưƳƽŶƴŝƮǀƀƤţšŶƯ ƽŚ ƸƿźǀĭƮǀưƈ ţƪƯŚ ƃƹƵŵƺ ŝƾ ƬƧƽŚ ƷŻŚǀƳƾ ƴǀŝƂǀ ěź ŝ šřżºǀƸŬţśŚŴŤƳřƖƿŻƺţƽŚƷŹŚŞƳřƪŰƯśŚŴŤƳřƪǀŞƣŻřƦƿĦţřźŤſř ƹŶºƿŶūƽŚƷźǀƀºƯŵŚŬƿřšLJƺƈŰƯƕƺƳśŚŴŤƳřƖƿŻƺţŶƴƿōźƟƹ šŶºƯƱŚºǀƯƽżºƿŹƶºƯŚƳźŝŹŵŢºſřƱŚƿźŤƄƯƽŚƋŚƤţƾƴǀŝƂǀě ƖƿŻƺţƽŚƷƶŤƃŚŞƳřƲǀǀƘţƱŚƿźŤƄƯƽŶƴŝƶŤſŵƱƺĤưƷƽŵŹřƺƯ
ƕƺºưŬƯƱŵƺºưƳƪƣřŶºůƝŶºƷŚºŝƶǀƬƤƳƪƿŚſƹŻřƦƿźƷƾŝŚƿźǀƀƯ šŶƯƵŚţƺƧƽżƿŹƶƯŚƳźŝŹŵŵźǀĮǀƯŹřźƣźƔƳŵŹƺƯƖƿŻƺţƽŚƷƶƴƿżƷ ƾƫřƺºţƲǀºǀƘţƶºƳřŻƹŹƪƤƳƹƪưůšŚǀƬưƗƽŶƴŞƳŚƯŻƱƺģƾƬƿŚƀƯ
ŵŹƺºƯƖºƿŻƺţšŚºǀƬưƗƶºŝƪƿŚºſƹƆǀƈŴţƹƪƤƳƹƪưůšŚǀƬưƗ
>è@ŶƃŚŞǀƯƶūƺţ źǀƀƯƪƿŚƀƯŹŵžƿƹźſŶŞſƾŝŚƿƶƴǀƸŝƕƺƋƺƯƶŝƲŤųřŵźěƵŻƹźƯř ŹƺŰƯƩƺůŶƃŚŝŹřżƟřŢŴſƶūƺŤƯƶƨƳōŻřƪŞƣƶǀƬƤƳƪƿŚſƹƾŝŚƿ ƹ ƽŹƹ ƵźƸŝ ƂƿřżƟř ŶƿŶū ƽŚƸƃƹŹ ƾƴƘƿ ŶƳżǀƯ Źƹŵ ŹřżƟř ƭźƳ źƨƠŝƶƨƳōŻřƪŞƣƹŶƳřŵƾưƳƖŝŚƴƯƂƿřżƟřŹŵŚƟźƇřŹƶƴƿżƷƂƷŚƧ ƵĦƿƹŢǀưƷřŶƴƃŚŝŶƿŶūƖŝŚƴƯƽřźŝƾƟŚƋřƽŹřŸĭƶƿŚƯźſƹƶƘſƺţ
Ţſř ƪŗŚƣ ƾſźŤſŵ Źŵ ƖŝŚƴƯ Żř źŤƸŝ ƶģźƷ ƽźǀĭŹŚƨŝ ƽřźŝ ƽř ƾŝŚƿźǀƀƯ Źŵ ƶƧ ƾŤƿźƿŶƯ šŚưǀưƈţ Żř ƂŴŝ Ʊō źŤƸŝ šŹŚŞƘŝ ƶƧ Ƶŵƺŝ šŶƯ ƱŚǀƯ šŚưǀưƈţŢſřźƔƳ ŵŹƺƯ źŤƄǀŝ ƶǀƬƤƳ ƪƿŚſƹ ƶƯŶƤƯæ
ŵŹƺºƯƱƺƴƧŚţŻŚŝźƿŵŻřƱōŢǀưƷřƹƶǀƬƤƳƪƿŚſƹƾŝŚƿźǀƀƯƕƺƋƺƯ ŚºƷƮŤƀºǀſƲƿźţƩƺưƘƯŢſřƵŵƺŝƱŚƷƹĦěƂƳřŵƹƲǀƤƤŰƯƶūƺţ ŶºƴģƶºǀƬƤƳƪƿŚºſƹƾŝŚºƿźǀƀºƯƶƬŘƀºƯƖºƿŻƺţƹƂŴěƽŚǀƳŵŹŵ
ƱŵƺºưƳƪƣřŶºůƝŶƷŚŝƾŰƐſŶƴģƹƾƫƺƈŰƯŶƴģóƾƷŚĮŤƀƿř
>æ@ŶƃŚŝƾƯƖƿŻƺţƽŚƷƶƴƿżƷ
ŻřƶºƴǀƸŝƵŵŚƠŤſřƱōƝŶƷƶƧŢſřƾŤǀƫŚƘƟƶǀƬƤƳƪƿŚſƹƾŝŚƿźǀƀƯ
ƶºŝƲǀºƘƯŶºƗƺƯŹŵƱŚƿźŤƄƯƽŚƋŚƤţƲǀƯŚţŹƺƔƴưŝƖƿŻƺţƖŝŚƴƯ
ƲºƿřŹŵŶºƃŚŝƾºƯƶºƴƿżƷƪƣřŶºůŚºŝƲǀƘƯƱŚƨƯŹŵƹƲǀƘƯƱřżǀƯ ƽźºſƦºƿƭŚºŬƳřƶŝŻŚǀƳƽźŤƄƯƶŝƩƺƈŰƯźƷƪƿƺŰţŚƷƮŤƀǀſ ƪºưůźĮƳŚºǀŝƮŤƀǀſŻřƶƬůźƯźƷŢſřƞƬŤŴƯƪůřźƯŹŵšŚǀƬưƗ ƶºƐƤƳƶºŝƶºƐƤƳƦºƿŻřƲǀºƃŚƯŶƴģŚƿƦƿƎſƺţLJŚƧŶƴģŚƿƦƿ
ƱŚƿźŤƄƯřŹLJŚƧšŚǀƬưƗƭŚŬƳřƶƬůźƯźƷƮŤƀǀſƲƿřŹŵŢſřźĮƿŵ
ŶƴƨǀƯźŤƨƿŵżƳƾƿŚƸƳ ƖºƿŻƺţƽŚºƷƶºƴƿżƷƩźºŤƴƧƽŚºƸƷřŹƲƿźºŤƸŝƹƲƿźŤưƸƯŻřƾƨƿ ƽřźºŝŵƹŶºŰƯƖŝŚƴƯƆǀƈŴţšŚǀƬưƗŵŹƺƯŹŵŮǀŰƇƽźǀĭƮǀưƈţ
ŭƺƐºſŚƷźǀƀƯŹŵšLJƺƈŰƯŻřƦƿźƷƽřźŝƖƿŻƺţƶŤƃŚŞƳřƲǀǀƘţ ƭŶºƗƶǀƬƤƳƪƿŚſƹƾŝŚƿźǀƀƯƽŚƸƫŶƯŹŵřźƿŻŢſřƞƬŤŴƯƾůřƺƳƹ ƽŚƷŹŚŞƳřŹŵƽŵƺūƺƯƂƿřżƟřƶǀƬƤƳƪƿŚſƹŢǀƟźƓŻřƪƯŚƧƵŵŚƠŤſř
ƮŤƀǀſƶŝřŹƽŵŚƿŻƶƴƿżƷƾƳLJƺƏƾŝŚƿźǀƀƯƹƖƿŻƺţƞƬŤŴƯƪůřźƯ
>ç@ŶƴƨǀƯƪǀưŰţ
êæƽźĭŹŚƧŵřŵźƸƯƹƽźƸĜſƽŶƸƯŶưŰƯƹƾƫƺƈŰƯŶƴģƾŰƐſŶƴģƾŝŚƿźǀƀƯƪŗŚƀƯŹŵžƿƹźſŶŞſƾŝŚƿƶƴǀƸŝ
ƮǀƀƤţ źƿŻ ƶŤſŵ ƶſ ƶŝ ƾƬƧŹƺƐŝ ƶǀƬƤƳ ƪƿŚſƹ ƾŝŚƿźǀƀƯ ƶƬŘƀƯ
ŶƳƺƄǀƯ
ƱŚĭŶƴƴƧƲǀƯŚţŻřŻŚǀƳŵŹƺƯšŚƘƐƣƹƶǀƫƹřŵřƺƯƲǀƯŚţ 
ƶƳŚųŹŚƧƱƹŹŵŹŵƶŤųŚſƶưǀƳšŚƘƐƣƹŵřƺƯƾƿŚŬŝŚū 
ƱŚƿźŤƄƯƲǀŝŹŵƾƿŚƸƳšLJƺƈŰƯƖƿŻƺţƹƂŴě 
12687342275Downloaded from ijiepm.iust.ac.ir at 16:53 IRST on Saturday November 4th 2017

Downloaded from ijiepm.iust.ac.ir at 16:53 IRST on Saturday November 4th 2017

ƵŶƃ ƭŚưţ Ţưǀƣ ŶƇŹŵ 1050 Ʋǀŝ ƪƤƳƹ ƪưů ƽŚƷƶƴƿżƷ ƪưů ƽŚƷ ƶƴƿżƷ ƂƷŚƧ ƲƿřźŝŚƴŝ  ŶƷŶǀƯ ƪǀƨƄţ řŹ šLJƺƈŰƯ ŶƷřƺųšLJƺƈŰƯƵŶƃƭŚưţŢưǀƣƂƷŚƧźŝƾƸūƺţƪŝŚƣźǀŧŚţƪƤƳƹ ŵŹřƺƯ Żř ƦƿźƷŹŵ ŮǀŰƇ šŚưǀưƈţ Ÿųř ƶƧ ŚŬƳō Żř >ëé@Ţƃřŵ Ʊō ƽŹƹ ƵźƸŝ ƹ ƪƤƳƹ ƪưů ƮŤƀǀſ ŵźƨƬưƗ ƂƿřżƟř ƽƹŹźŝ ơƺƟ ƖƿŻƺţƹƂŴěƽŚƸŤƧźƃŢŝŚƣŹŢǀƬŝŚƣƹƾƿŚƳřƺţŹŵƹƵŵƺŝŹřŸĭźǀŧŚţ ƪůƹƽŻŚƀƫŶƯƽŚƸƃƹŹŵƺŞƸŝƹƶƘſƺţŵŹřŵƽřƵŶƴƴƧƲǀǀƘţƂƤƳ ƶǀƬƤƳƪƿŚſƹƾŝŚƿźǀƀƯƪŗŚƀƯŹŵžƿƹźſŶǀſƾŝŚƿƶƴǀƸŝƽŚƸƫŶƯ
ƱŵƺưƳƪƣřŶůƝŶƷŚŝƾŰƐſŶƴģƹƾƫƺƈŰƯŶƴģƾƷŚĮŤƀƿřŶƴģ ƾſŹźŝ ŵŹƺƯ ƶƫŚƤƯ ƲƿřŹŵ ƹ ƶŤƃřŵ ƽŵŚƿŻ ŢǀưƷř ƖƿŻƺţ ƽŚƷƶƴƿżƷ ƾŝŚƿźǀƀƯ ƪŗŚƀƯ Źŵ ƾŤƿźƿŶƯ šŶƯ ƱŚǀƯ šŚưǀưƈţ ŵźǀĭƾƯ Źřźƣ Źŵ ƮƸƯ šŚưǀưƈţ ŶƃŚŞǀƯ ƽźŤƄǀŝ ŢǀưƷř ƽřŹřŵ ƶǀƬƤƳ ƪƿŚſƹ ƲǀǀƘţƱŚƿźŤƄƯƽŶƴŝƶŤſŵƪƯŚƃƢǀƤŰţƲƿřƾŝŚƿźǀƀƯƪŗŚƀƯ
ƝŶƷ Śŝ ƶǀƬƤƳ ƪƿŚſƹ Żř ƦƿźƷ ƾŝŚƿźǀƀƯ ƹ ƖƿŻƺţ ƽŚƷ ƶŤƃŚŞƳř ƽŚƸƫŶƯŹŵřźƿŻŶƃŚŝƾƯƖƿŻƺţƽŚƷƶƴƿżƷƕƺưŬƯƱŵƺưƳƪƣřŶů Żř ŶƘŝ ƾŰƐſŶƴģ ƹ ƾƫƺƈŰƯ Ŷƴģ óƾƷŚĮŤƀƿř Ŷƴģ ƾŝŚƿźǀƀƯ
ƖƿŻƺţ ƶŤƃŚŞƳř ƵŻřŶƳř ƲǀǀƘţ ƶŝ ŢŝƺƳ ƱŚƿźŤƄƯ ƽŶƴŝƶƃƺų šŚǀƬưƗ ƞƬŤŴƯ ƾůřƺƳ ƹ ŭƺƐſ ŚƷźǀƀƯ Źŵ šLJƺƈŰƯ Żř Ʀƿ źƷ ƽřźŝ ƪƇřƦƿƱřƺƴƘŝ>ì@ŵƺƄǀƯƭŚŬƳřƾŝŚƿźǀƀƯšŚǀƬưƗžĜſŵƺƄǀƯ ƱŚƯŻ ŶƃŚŝ źŤĭŹżŝ ƪƤƳƹ ƪưů ƪƿŚſƹ ƶģźƷ ŢƠĭ ƱřƺţƾƯ ƾƬƧ
ŶŝŚŞǀƯƂƷŚƧźǀƀƯƾƏƱŚƯŻƹƶŤƟŚƿƂƿřżƟřƽŻřŶƳřŹŚŝƹƽźǀĭŹŚŝ ƶŤƃŚŞƳř ƲǀǀƘţ ƽŶƴŝ ƶƃƺų ƽŚƷŢſŚǀſ ƢǀƠƬţ ŽŚſř Ʋƿřźŝ >í@
ƹŭƺƐſƪůřźƯŻřƦƿźƷŹŵƶǀƬƤƳƪƿŚſƹƾŝŚƿźǀƀƯƹƖƿŻƺţƽŚƷ
>î@ŶƴƧƾƯƪƣřŶůřŹƖƿŻƺţƮŤƀǀſƽŚƷƶƴƿżƷƞƬŤŴƯƾůřƺƳ
ƽřźºŝŶºƿŶŰţƹśŚƘƄƳřƮŤƿŹƺĮƫřƦƿ>æå@ƱřŹŚƨưƷƹšŹƺěLJ 
ŶºƳŵƺưƳƽŹƹōŵŚºƿƱŚƄƿřŶƳŵƺưƳƶŗřŹřMDVRPƪŗŚƀƯƪů
ŜºſŚƴƯƦºģƺƧƪŗŚƀºƯƪºůƽřźºŝƎºƤƟŚƷƮŤƿŹƺĮƫřƲƿřƶƧ
ŶƴŤƀƷ
ƭŚºųŵřƺºƯƪºƤƳƹƪºưůƶƬŘƀºƯ>ææ@ƭŚųŹŚƯƹŢſřźĤǀƯŚſ 
Ŝ ƫŚƣŹŵřŹšŚƀ ǀſŚţŻřƽřƶ ƗƺưŬƯƶ ŝƵŚĮŤƀ ƿřƲƿŶ ƴģŻř
ŶƳŵźƧƶƫƺƯźƟMDVRP
ƽřźºŝƽŻŚºſƶƴǀƸŝƶƿLJƶſƩŶƯƦƿ>æç@ƱřŹŚƨưƷƹƱƺŤſřƹ 
ŶƳŵƺưƳƶŗřŹřƽŶǀƫƺţšŚŬƳŚųŹŚƧšLJƺƈŰƯƪƤƳƹƪưůƮŤƀǀſ
ƝŸºůŚºŝƶºƿLJƶºſƩŶºƯƪůƽřźŝ>æè@ƱřŹŚƨưƷƹŹŚǀŞƯŚƳ 
řŹƱōžĜºſƹƪƿŶŞţƶƿLJƹŵƩŶƯƶŝřŹƶƬŘƀƯƾƳŚǀƯƽŚƷŹŚŞƳř
ƶºƿLJŶƴģƽŚƸƫŶƯƶưƷƶƧŶƴŤƃřŵƵŶǀƤƗƱŚƄƿřŶƳŵƺưƳƪů ŶƃŚŞǀƯƪůƪŝŚƣƶƿLJƹŵƽŚƸƫŶƯŚŝ ƾŝŚƿźǀƀƯƹƖƿŻƺţƽŚƷƶŤƃŚŞƳřƱřżǀƯƲǀǀƘţƱŚƿźŤƄƯƽŶƴŝƶŤſŵ Żř ŶƘŝ ƖƿŻƺţ ƽŚƷƮŤƀǀſ Źŵ řźƿŻ Ţſř Ʊō ƮƸƯ ƪŗŚƀƯ ƶƬưū Żř ƽƹŹźŝ šŚǀƬưƗ ƪưů šřżǀƸŬţ ƹ ƱŚƿźŤƄƯ ƽŚƋŚƤţ ƲǀǀƘţ šŹƺƇ ƾŝŚƿźǀƀƯ ƹ ƖƿŻƺţ ƶŤƃŚŞƳř ƱřżǀƯ ƱŚƿźŤƄƯ ƽŶƴŝƶŤſŵ ƹ ƩźŤƴƧ ƽŚƸƷřŹ ƲƿźŤƸŝ ƹ ƲƿźŤưƸƯ Żř ƾƨƿ ŽŚſř Ʋƿřźŝ ŵźǀĮǀƯ ƽŶƴŝ ƶŤſŵ ƅƺƈųŹŵ ƽźǀĭ Ʈǀưƈţ ƖƿŻƺţ ƽŚƷƶƴƿżƷ ƂƷŚƧ
ŻřƦƿźƷƽřźŝŮǀŰƇƾŝŚƿźǀƀƯƹƖƿŻƺţƶŤƃŚŞƳřƲǀǀƘţƱŚƿźŤƄƯ
ŶƃŚŝƾƯŵƺƿźěźƷŹŵƶǀƬƤƳƪƿŚſƹ ŚţƽżƧźƯŹŚŞƳřƲǀŝźǀƀƯŢǀưƷřƶǀƬƤƳƪƿŚſƹƾŝŚƿźǀƀƯƪŗŚƀƯŹŵ ƹ ŹŚƨƃō ŹŚǀƀŝ ƱŚƿźŤƄƯ ŹŚŞƳř Śţ ƾƳŚǀƯ ƽŚƷŹŚŞƳř ƹ ƾƳŚǀƯ ƽŚƷŹŚŞƳř
ŶƴƨǀƯƪǀưŰţƮŤƀǀſźŝƽŵŚƿŻƶƴƿżƷLJƺưƘƯƹŢſřźƿŸěŚƳŹŚƨƳř Ţſř ŹřŵŹƺųźŝ ƽř ƵĦƿƹ ŢǀưƷř Żř ŚƷźǀƀƯ Ʋƿř ƩźŤƴƧ řŸƫ ƹ
ƱŚƿźŤƄƯŶƿŚŝƾŝŚƿźǀƀƯšŚǀƬưƗŻřƪŞƣƪƇřƦƿƱřƺƴƘŝƲǀƴĤưƷ šŚǀƬưƗ ƖƿŻƺţ ƶŤƃŚŞƳř ƱřżǀƯ ƲǀǀƘţ Żř žě ƹ ƵŶƃ ƽŶƴŝ ƶƤŞƏ ŹŵŚŝƶƧƮǀŤƀƷƾƿŚƷźǀƀƯƩŚŞƳŶŝŚƯƲƿřźŝŚƴŝŵƺƃƭŚŬƳřƾŝŚƿźǀƀƯ ƽŚƋŚƤţ ƶƴƿżƷ ƪƣřŶů Śŝ ƪưů ƪƿŚſƹ ŢƿŵƹŶŰƯ ƲŤƟźĭ źƔƳ ƽƹŹźŝ ŶǀƧŚţ ƢǀƤŰţ ƲƿřŹŵ ŶƴƧ ƲǀƯŚţ ŹźƤƯŶƗƺƯ Źŵ řŹ ƱŚƿźŤƄƯ ƱŚƿźŤƄƯ ƽŶƴŝ ƶƤŞƏ ƽƹŹ ƅŚų ŹƺƐŝ ƹ šŶƯ ƱŚǀƯ ƽżƿŹ ƶƯŚƳźŝ ƾŝŚƿźǀƀƯ ƶƬŘƀƯ ƪů Ţſř ƾŝŚƿźǀƀƯ ƹ ƖƿŻƺţ ƶŤƃŚŞƳř ƲǀǀƘţ ƱŚƿźŤƄƯ ƽŶƴŝ ƶƤŞƏ  ƱŚƿźŤƄƯ ƽŚƋŚƤţ ƾƴǀŝ Ƃǀě ƭżƬŤƀƯ ƾŝŚƿźǀƀƯ ƹ ƖƿŻƺţ ƶŤƃŚŞƳř ƲǀǀƘţ ƪƤƳ ƹ ƪưů ƪƿŚſƹ ƆǀƈŴţ
ƹŮǀŰƇšŹƺƈŝƪůřźƯƶưƷŹŵšŚưǀưƈţƶƧƾţŹƺƇŹŵŶƃŚŝƾƯ
ŢſřƖƿŻƺţƹƂŴěƽŚƷƶƴƿżƷƱŶƃƪƣřŶůŦƗŚŝŵƺƃƭŚŬƳřƖƣƺưŝ ƱŚĭƹŚƳ ŢƿźƿŶƯ ƪƤƳƹ ƪưů ŦŰŝŹŵ ƽŶǀƬƧƹƮƸƯ ƪŗŚƀƯ Żř ƾƨƿ ƹƽŹƹōƖưūšŚƯŶųƶŗřŹřƽřźŝƵŵŚƠŤſřŵŹƺƯƲĮưƷŚƳƶǀƬƤƳƪƿŚſƹ
ƽŚƋŚƤţƹƶƋźƗŚŝƱŚƿźŤƄƯƹƱŚĭŶƴƃƹźƟƽřƶƗƺưŬƯƲǀŝƖƿŻƺţ ƮŤƀǀſźƿŶƯŶƃŚŞǀƯƶƟźƇƶŝƱƹźƤƯƹƽŵŚƈŤƣřƽřƶƳƺĮŝƆŴƄƯ ŵŹƺƯƶǀƬƤƳƪƿŚſƹŵřŶƘţƅƺƈųŹŵŶƿŚŝŚƸƴţƶƳƖƿŻƺţƹƽŹƹōƖưū ƱŚƿźŤƄƯƭřŶƧƶƧŶƴƧƆŴƄƯŶƿŚŝƶƨƬŝŵźǀĮŝƮǀưƈţƵŵŚƠŤſř ƪƣřŶů Śŝ ƾƫřƺţ ƹŶƳźǀĮŝ žƿƹźſŶƿŚŝ ƽř ƶǀƬƤƳ ƪƿŚſƹƶģ Ǝſƺţ ƶƧƾţLJƺƈŰƯŶƴƧƆŴƄƯżǀƳřŹƽŵƺūƺƯƹƪƤƳƹƪưůƶƴƿżƷ ƽŹƹōƖưūšLJƺƈŰƯƹƵŶƃƽźǀĭŹŚŝŹŚŞƳřŹŵŵƺƃƖƿŻƺţŢſřŹřźƣ ƆǀƈŴţŚŝšŚǀƬưƗƲƿřŶƳƺƃƾƯƵŶƳřŵźĭŻŚŝŹŚŞƳřƶŝřŵŶŬƯżǀƳƵŶƃ ŹŚŞƳřƦƿŻřźǀƀƯźƷŵƺƄǀƯƕƹźƃźǀƀƯƦƿƶŝƶǀƬƤƳƶƬǀſƹƦƿ ŶƿŚŝ źǀƀƯ źƷ ƽřźŝ ŵƺƃƾƯ ƮŤų Ʊō ƶŝ řŵŶŬƯ ƹ ŵƺƄǀƯ ƕƹźƃ ŵƺƃ ƲǀƯŚţ ƪưů ƪƿŚſƹ ŢǀƟźƓ ƹ ƽŹŚƧ ƱŚƯŻ ƽŚƷ ŢƿŵƹŶŰƯ ƎſƺţŶƿŚŝƽźŤƄƯźƷŶƃŚŞƳŻŚŬƯŚƋŚƤţƮǀƀƤţźĭřƲƿřźŝƵƹLjƗ ƾŝŚƿźǀƀƯ ƶƬŘƀƯ ƕƺƳ ƲƿŶƴģ ƱƺƴƧŚţ ŵźǀĮŝ žƿƹźſ ƶƬǀſƹ Ʀƿ ŶƳřƶŤƟźĭŹřźƣƾſŹźŝƹƶƘƫŚƐƯŵŹƺƯƕƺƋƺƯšŚǀŝŵřŹŵƶǀƬƤƳƪƿŚſƹ ŶƳŹřŵƵŹŚƃřƾţƹŚƠŤƯƽŵźŝŹŚƧƹƾƬưƗšLJŚůƶŝƪŗŚƀƯƲƿřƶģźĭř ƽřźŝ ƶǀƬƤƳ ƪƿŚſƹ źŧƺƯ ƹ řŹŚƧ ŢƿźƿŶƯ ƶƬŘƀƯźŝ ŚƸƳō ƾĮưƷ ƾƫƹ ƽŚƷƶƴƿżƷŶƴŤƀƷżƧźưŤƯƱŚƿźŤƄƯŻřƽřƶƗƺưŬƯƶŝƾƷŵžƿƹźſ
ƽźĭŹŚƧŵřŵźƸƯƹƽźƸĜſƽŶƸƯŶưŰƯƹƾƫƺƈŰƯŶƴģƾŰƐſŶƴģƾŝŚƿźǀƀƯƪŗŚƀƯŹŵžƿƹźſŶŞſƾŝŚƿƶƴǀƸŝêç
ƁƹŹ ŽŚſřźŝ ƦǀŤſŹƺǀƷ ƁƹŹ Ʀƿ >çè@ ŢƿřŹ ƹ ƥŹLjƧ 
ƶƀƿŚƤƯƢƿźƏŻřƁƹŹƲƿřŵźƨƬưƗŶƳřƵŵřŵƶƘſƺţƽŻŚſƵźǀųŷ Ţſř ƶŤƟźĭŹřźƣ ƾŝŚƿŻŹř ŵŹƺƯŶƿŶŰţ ƹ śŚƘƄƳř ƲǀŗŚě ƱřźƧ Śŝ ƶŤųŚƴƃ ƱƺŤſźǀƀƯ Ŷǀƫƺţ ƁƹŹ ƲƿźŤƸŝ ƱřƺƴƘŝ ƁƹŹ Ʋƿř
ŚŝƹƵŶƃƕƹźƃƶūƺƯźǀƛśřƺūƦƿŚŝƁƹŹƲƿřŢſřƵŶƃ
ŵŹřŵƶƴƿżƷƂƷŚƧŹŵƾƘſŚƷźǀƀƯŻřŚţƹŵźƷŜǀƧźţ
126873-142232Downloaded from ijiepm.iust.ac.ir at 16:53 IRST on Saturday November 4th 2017

Downloaded from ijiepm.iust.ac.ir at 16:53 IRST on Saturday November 4th 2017

ŮƐſŹŚƸģƶŝřŹ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
126873469814Downloaded from ijiepm.iust.ac.ir at 16:53 IRST on Saturday November 4th 2017

Downloaded from ijiepm.iust.ac.ir at 16:53 IRST on Saturday November 4th 2017

ƲƿřƽŚƷŢƿŵƹŶŰƯƹƝŶƷƖŝŚţƽźǀĭƮǀưƈţƽŚƷźǀƜŤƯŚƷźŤƯřŹŚě ŵŵźĮǀƯŮƿźƄţźƿŻšŹƺƈŝŵƹŶŰƯŚƳƽżƿŹƶƯŚƳźŝƢƟřƦƿŹŵƩŶƯ
ƽźǀĭƮǀưƈţƽŚƷźǀƜŤƯƹŚƷźŤƯřŹŚěƞƿźƘţçæ
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 æé
126873227803Downloaded from ijiepm.iust.ac.ir at 16:53 IRST on Saturday November 4th 2017

Downloaded from ijiepm.iust.ac.ir at 16:53 IRST on Saturday November 4th 2017

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ŜƿřźƋƦưƨŝŽŚſřƲƿřźŝŶƳźǀĭ
12687334672Downloaded from ijiepm.iust.ac.ir at 16:53 IRST on Saturday November 4th 2017

Downloaded from ijiepm.iust.ac.ir at 16:53 IRST on Saturday November 4th 2017

ƦºƿƶƬŘƀƯ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
.



قیمت: تومان


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