A Hybrid Effective Genetic Algorithm for Solving the Vehicle Routing Problem

A. Zafari, S.M. Tashakori Hashemi & M. Yousefi Khoshbakht*

A.Zafari, Lecturer, Payame Noor University (PNU).
S.M. Hashemi, Professor, Amirkabir University of Technology.
M. Yousefi KHoshbakht, Lecturer, Islamic Azad University Hamedan Branch, Member of Young Researcher Club (YRC).


Genetic Algorithm, Premature
Convergence, NP-hard
Problems, Vehicle Routing
Problem The Vehicle Routing Problem (VRP) is one of the most important combinational optimization problems that has nowadays received much attention of researchers and scientists. In this problem, the objective is to minimize the cost traveled by several vehicles that start to move simultaneously from depot and come back to depot after visiting customers if at first each node is visited only once by one of the vehicles and at second each vehicle does not load more than its capacity during the route.
This paper presents a hybrids meta-heuristic algorithm for solving the classical vehicle routing problem. At the first stage, a modified genetic algorithm for finding a suboptimal solution is applied in which a new crossover method for combination chromosomes is proposed. Then at the second stage, the 3-opt algorithm is used for finding better solutions. Extensive computational tests on standard instances from the literature confirm the effectiveness of the presented approach.
æèíîçæŶƬūçƵŹŚưƃ ŶǀƫƺţŢƿźƿŶƯƹƖƿŚƴƇƾſŶƴƸƯƾƬƬưƫřƲǀŝƶƿźƄƳ’


ƾƿŚŬŝŚūƶƴƿżƷƶƴǀưĩƲǀǀƘţƝŶƷƶƫŚƀƯƲƿřŹŵŵźǀĭƾƯŹřźƣƱřŶƴưƄƳřŵƹƱŚƤƤŰƯƶūƺţŵŹƺƯ šŚƣLjƯŻřŶƘŝƹŶƴƴĩƾƯŢĩźůƶŝƕƹźƃLJŚĩŹŚŞƳřŻřƱŚƯżưƷŹƺƐŝƶĩŢſřƶǀƬƤƳƶƬǀſƹƲƿŶƴģ
ƪƿŚſƹƲƿřŻřƾĪƿƎſƺţƎƤƟƵźĭźƷLJƹřƶĪƳōƍźƃƶŝŶƳŵźĭƾƯŻŚŝŹŚŞƳřƶŝŚƷƽźŤƄƯƱŵźĩ ĨǀŤƳĥƮŤƿŹƺĮƫř
ƭŚţ NPƪŗŚƀƯ
ííîæçƩƺƇƹŲƿŹŚţ íîèêŜƿƺƈţŲƿŹŚţ
zafari_math@yahoo.com Payame Noor University (PNU)ŹƺƳƭŚǀěƵŚĮƄƳřŵŽŹŶƯƽźƠƓƾƬƗ
hashemi@aut.ac.irƱřźƸţźǀŞĩźǀƯřƾŤƘƴƇƵŚĮƄƳřŵƾƋŚƿŹƵŶĪƄƳřŵŹŚǀƄƳřŵƾưƃŚƷƽźĪƄţƽŶƸƯŶǀſźŤƧŵ khoshbakht@aut.ac.irƱřƺūƱřźĮƄƷƹĦěƵŚĮƃŚŝƺƌƗƱřŶưƷŶůřƹƾƯLjſřŵřŻōƵŚĮƄƳřŵƾŝźƯŢŴŞƃƺųƾƠſƺƿŶǀŬƯ
ŵŚƸƴƄǀěƶǀƬƤƳƶƬǀſƹƾŝŚƿźǀƀƯĨǀſLjĩƶƫŚƀƯƪůƽřźŝƾŞǀĩźţƽŹŚĪŤŝřřźƟƁƹŹƾƗƺƳƶƫŚƤƯƲƿř ƶŤƟźĭ ŹŚĪŝ śƺų ƲǀƸŝ źƿŻ śřƺū Ĩƿ ƲŤƟŚƿ ƽřźŝ ĨǀŤƳĥ ƾůLjƇř ƁƹŹ Ʃƹř ŻŚƟ Źŵ ŶƴĩƾƯ
ƵŵŚƠŤſř ƶƳŚĭƶſ ƵŶƴƷŵ ŵƺŞƸŝ ƾƬŰƯ ƽƺŬŤƀū ƮŤƿŹƺĮƫř Żř źŤƸŝ ƽŚƷśřƺū ƲŤƟŚƿ ƽřźŝ ƭƹŵ ŶƴĩƾƯšŚŞŧřřŹƽŵŚƸƴƄǀěƁƹŹƾƿřŹŚĩƽŹŚĪŤŝřřźƟźĮƿŵƽŚƷƁƹŹŚŝƁƹŹƲƿřƶƀƿŚƤƯŵƺƃƾƯ

ƽřźŝƽźŧƺƯŹŚĪƷřŹƽřŹřŵŚƷƮŤƿŹƺĮƫřŻřƕƺƳƲƿřƶƳŚƠſŚŤƯƾƫƹŵŹřŶƳ ƽŚƷƶƴǀƸŝ Źŵ ƖƣřƺƯ źŤƄǀŝ Źŵ ƹ ŶƴŤƀǀƳ ƾƬŰƯ ƶƴǀƸŝ ƍŚƤƳ Żř ŹřźƟ ƶŝ ƱřƺţƾƯ ŚƷƮŤƿŹƺĮƫř Ʋƿř Żř ƶƳƺưƳ ƽřźŝ ŶƴŤƟřƾƯ źǀĭ ƾƬŰƯ
ƵŹŚƃř >î@ >í@ƺūƶƟźƇ ƾůLjƇř ƮŤƿŹƺĮƫř ƹ >ì@ƺūƶƟźƇ ƮŤƿŹƺĮƫř
ƝLjųźŝ ƮŤƿŹƺĮƫř ƽřźūř ƱřżǀƯ ƶĩ ƽŹŚĪŤŝřřźƟ ƽŚƷƁƹŹ Źŵ ŹŵŚŞƿźƤţŚƷśřƺūŢſřƶŤƀŝřƹźŝŹŚĩƮǀưƈţƶŝƽŹŚĪŤŝřƽŚƷƁƹŹ ƢǀƣŵƽŚƷƁƹŹŻřźŤưĩƹƽŹŚĪŤŝřƽŚƷƮŤƿŹƺĮƫřŻřźŤƄǀŝƱŚƯŻĨƿ ƽŚƷśřƺūŻřŚƷƁƹŹƲƿřƽŚƷśřƺūLJƺưƘƯƶģźĭřŶƿōƾƯŢſŶŝ ƾƿŚƷŹŚĪƷřŹŻřŚƷƮŤƿŹƺĮƫřŻřƶƳƺĮƴƿřƹŢſřźŤƸŝƽŹŚĪŤŝřƽŚƷƁƹŹ ŶƴŤƠǀƳźǀĭƾƬŰƯƽŚƷƶƴǀƸŝŹŵƲĪưƯŶůŚţƶĩŶƴƴĩƾƯƵŵŚƠŤſř ƶĩ ŶƳŹřŵ ŵƺūƹ ŚƷƮŤƿŹƺĮƫř Ʋƿř Źŵ ƽŵŚƿŻ ƽŚƷźŤƯřŹŚě ŚƯř æ ƪĪƃ ŵŚƿŻ ƮŬů Ʋƿř Ŷƿō ŢſŶŝ ƾŝźŬţ šŹƺƈŝ ƹ źŝŹŚĩ Ǝſƺţ ŶƿŚŝ ƶŝŚƄƯ ƽŚƷřźĪţ Źŵ ŶƴƳřƺŤƳ ŚƷƮŤƿŹƺĮƫř ƶĩ ŵƺƃƾƯ ŜŞſ ŚƷźŤƯřŹŚě
ƶĩŢƟźĭƶŬǀŤƳƱřƺţƾƯƲƿřźŝŚƴŝŶƳŹƹōŢſŶŝřŹƾƳŚƀĪƿƽŚƷśřƺū śřƺū ƶŝ ƱŶǀſŹ ƽřźŝ ŢŝŚŧ ƩřƹŹ Ĩƿ ƽřŹřŵ ŚƷƮŤƿŹƺĮƫřŻř ƶƳƺĮƴƿř ƽŻŚŝŚƷƮŤƿŹƺĮƫřƲƿřŹŵřŹƽŵŚƿŻƂƤƳƾƟŵŚƈţƽŚƷźŤƯřŹŚěƹƵŵƺŞƳ ƽŚƷƁƹŹ ƶŝ ƱřƺţƾƯ ŚƷƮŤƿŹƺĮƫř Ʋƿř Żř ƩŚŨƯ ŹƺƐŝ ŶƴƴĩƾƯ
ĨǀŤƳĥ ƮŤƿŹƺĮƫř >ææ@ ƾƬǀƳō ƽŻŚſƶǀŞƃ >æå@ ƕƺƴưƯ ƽƺŬŤƀū
ŵźĩƵŹŚƃř>æì@ĨǀŤưƯƮŤƿŹƺĮƫřƹ>æë@ ƱŚĭŶƳźěƮŤƿŹƺĮƫř

ƾţŚŞǀƧźţƽŻŚſƶƴǀƸŝƶƫŚƀƯæ ƪĪƃ
ƾƴǀưŴţ ƽŚƷƮŤƿŹƺĮƫř Żř ƾŞǀĩźţ ƶĩ ƾŞǀĩźţ ƽŚƷƮŤƿŹƺĮƫř Źŵ ƺŰƳƶŝŚƷƮŤƿŹƺĮƫřŻřƭřŶĩźƷƽŚƿřżƯŻřƶĩŢſřƵŶƃƾƘſŶƴŤƀƷ ƽřŹřŵƽŹŚĪŤŝřƽŚƷƮŤƿŹƺĮƫřƶģźĭřƩŚŨƯŹƺƐŝŵƺƃƵŵŚƠŤſřƾŝƺų
Ʋƿř ŚƯř ŶƴŤƀǀƳ ƽŹŚĪŤŝřřźƟ ƽŚƷƁƹŹ ƶŝ ŢŞƀƳ ƾŝƺų ŚŤŞƀƳ śřƺū
Źŵ ƱřƺţƾƯ ƲƿřźŝŚƴŝ ŶƴƿōƾƯ ŢſŶŝ ħŶƳř ƱŚƯŻ Ĩƿ Źŵ řŹ śřƺū
ƲƿźţŵźŝŹŚĩźě ƹ ƲƿźŤưƸƯ Żř ƾĪƿ ƶǀƬƤƳ ƶƬǀſƹ ƾŝŚƿźǀƀƯ ƶƫŚƀƯ
ƽŻŚſƶƴǀƸŝ ƪŗŚƀƯ Źŵ Ɩǀſƹ ŹƺƐŝ ƶĩ Ţſř >æ@ƭŚţ NP ƪŗŚƀƯ ƶĩ Ţſř ŵŚƿŻ ŹŶƤƳō ƪŗŚƀƯ Żř ƶƳƺĮƴƿř ƕƺƴţ >ç@ŵŹřŵ ŵźŝŹŚĩ ŶƷŵƾƯ űŹ Ʊō Źŵ ƶĩ ƾƠƬŤŴƯ ƽŚƷŢƫŚů ƱŚǀŝ ƹ ŚƸƳō ƽŶƴŝƶŤſŵ
ëåƶƷŵŹŵƶƫŚƀƯƲƿřƶĩƾƳŚƯŻŻřŢſřźǀĭƱŚƯŻƹƪĪƄƯŹŚǀƀŝ ŽŚſřźŝ Ʊō Żř ƽŹŚǀƀŝ ƽŚƷŢƫŚů ŢƟźĭ Źřźƣ ƾſŹźŝ ŵŹƺƯ ŶƳŶƃƢŤƄƯƱōŻřŶƴŤƃřŵƾƘƣřƹƽŚǀƳŵŹŵƶĩƾţƹŚƠŤƯƽŚƷŵźŝŹŚĩ ƹ ŢƟŚƿŹŵ ĨǀſLjĩ ƕƺƳ ŶƴƳŚƯ ƽŵŚƿŻ ƽŚƷƶŴƀƳ Ʊƺƴĩř ƶĪƿŹƺƐŝ
ŶƳŹřŵŵƺūƹƹŻŚŝƕƺƳƾŤƄĭŻŚŝŢƟŚƿŹŵƹƪƿƺŰţƱŚƯżưƷƪƿƺŰţ źĮƿŵ ƪŗŚƀƯ ŶƴƳŚưƷ ƶƫŚƀƯ Ʋƿř Ʊŵźĩ ƪů ƽřźŝ ƾƬĩ ŹƺƐŝ
ƭřŶĩ źƷ ƶĩ ŶƳŹřŵ ŵƺūƹ ƽŵŚƿŻ ƽŚƷƁƹŹ ƾţŚŞǀĩźţ ƽŻŚſƶƴǀƸŝ řŹŚƷƁƹŹƲƿřƱřƺţƾƯƾƬĩŢƫŚůŹŵŶƴŤƀƷƾŞƿŚƘƯƹŚƿřżƯƽřŹřŵ
ŵźĩƽŶƴŝƮǀƀƤţƾƴǀưŴţƹƢǀƣŵƽŚƷƮŤƿŹƺĮƫřīŹżŝƶŤſŵƹŵƶŝ ƢǀƣŵśřƺūƱŵŹƹōŢſŶŝŶƴƳŚƯƶƫŚƀƯŹŵŵƺūƺƯźĮƿŵƝřŶƷřƶŤŞƫř ƩƺŞƣ ƪŝŚƣ ƱŚƯŻ Ĩƿ Źŵ śƺų śřƺū Ĩƿ ƱŶƯō ŢſŶŝ Śƿ ƶƫŚƀƯ Śŝ ƶŤſŵ ƹŵ Ʋƿř ƶŝ ŚƷƮŤƿŹƺĮƫř ƽŶƴŝƶŤſŵ ƶĩ ŵŵźĭƾƯ ŜŞſ
ƹŵ ƲƿřƾƯŚſřŻř ƶĩ ŹƺƐƳŚưƷ řźƿŻ ŵźƿŸĜŝƭŚŬƳř ƽźŤƄǀŝ ƱŚƴǀưƏř ƲǀƸŝ śřƺū ƶŝ Ƣǀƣŵ ƽŚƷƮŤƿŹƺĮƫř ŢſřŶǀě ŚƷƮŤƿŹƺĮƫř Żř ƶŤſŵ ƶŬǀŤƳ Źŵ ƹ ƽźŤƄǀŝ ƱŚƯŻ ŶƿŚŝ ƮŤƿŹƺĮƫř ŚƯř ŶƴŝŚƿƾƯ Ţſŵ ƶƫŚƀƯ ŹŵƵƹLjƘŝŶƴĩƝźƇŚƷśřƺūƲƿřƶŝƱŶǀſŹƽřźŝřŹƽźŤƄǀŝƶƴƿżƷ ƹ ƶŤƟźĭ Źřźƣ ƾſŹźŝ ŵŹƺƯ ƲĪưƯ ƽŚƷśřƺū ƾƯŚưţ Śƿ ŚƷƁƹŹ Ʋƿř ŚƿƹŶƿōŢſŶŝśřƺūƲƿźŤƸŝŚƸƳōƾƯŚưţƱŚǀƯŻřƶĩŵƺƃƾƯƾƘſ ŚƷśřƺūŻřƽřƶŤſŵƶƬůźƯźƷŹŵƹƵŶƃƽŶƴŝƶŤſŵŚƷśřƺūƶĪƴƿř ƕƺƳ Ʋƿř Żř ƩŚŨƯ ƽřźŝ ŵƺƃƾƯ ƶŤƃřŸĭ ŹŚƴĩ ƾƤƐƴƯ ƪƿLJŵ ŢƬƘŝ -ƮưǀƴǀƯƁƹŹ>è@ŢųŹŵƂƿŚưǀěƮŤƿŹƺĮƫřƶŝƱřƺţƾƯŚƷƮŤƿŹƺĮƫř Źŵ ŚƯř ŵźĩ ƵŹŚƃř >ë@ >ê@Ʊřźĩ ƹ ƶųŚƃ ƮŤƿŹƺĮƫř ƹ >é@ŢųŹŵ k ŹŵƹƵŵƺŝƾƴŨŤƀƯƵŶƗŚƣƲƿřŻřƾƴǀưŴţƽŚƷƮŤƿŹƺĮƫřƪŝŚƤƯƶƐƤƳ śřƺūŢſřƲĪưƯƶĩŶƴģźƷŶƴſŹƾƯśřƺūƶŝħŶƳřƱŚƯŻĨƿ
ƽŹŚĪŤŝř ƽŚƷƮŤƿŹƺĮƫř ƶŤſŵ ƶſ ƶŝ ŵƺų ŚƷƁƹŹ Żř ƶƳƺĮƴƿř ŵƺūƹ ƶĩ ƾưƸƯ ƶŤĪƳ ŶƳƺƃƾƯ ƽŶƴŝƶŤſŵ ƾŞǀĩźţ ƹ ƽŹŚĪŤŝřřźƟ ƽŵŚƿŻƽŚƷƾĭŶǀĤǀěŻřƶĩƽŹŚĪŤŝřƽŚƷƁƹŹŹŵƶĩŢſřƲƿřŵŹřŵ ƹŶƿōƾƯŢſŶŝħŶƳřƱŚƯŻĨƿŹŵƶƫŚƀƯśřƺūŶƴŤƀǀƳŹřŵŹƺųźŝ ƾƄƤƳ šƹŚƠŤƯ ƽŚƷśřƺū ƱŵŹƹō ŢſŶŝ Źŵ ƮŤƿŹƺĮƫř Ʊŵźĩ ŹřźĪţ

ƪŝŚƣšŚĪƳŵƺƃƵŵŹƹōźŝƶƫŚƀƯƵŶƴƷŵžƿƹźſ m ŻřƾĪƿƶƬǀſƺŝ
ŶƴƃŚŝ 0 ƶƐƤƳŹŵŶƿŚŝƮŤƿŹƺĮƫřƽřŶŤŝřŹŵƶǀƬƤƳƪŗŚſƹƶưƷ 
ŻřźŤƄǀŝƶĩŢƀǀƳŻŚŬƯƱŚƯŻĢǀƷŹŵƽřƵŶƴƷŵžƿƹźſĢǀƷ 
ƽřźŝ ŻŚŬƯ ŢǀƟźƓ Żř źŤƄǀŝ ŶƿŚŞƳ ŚƷƽźŤƄƯ ƽŚƋŚƤţ ĢǀƷ 
qi Q ƮǀƃŚŝ
ƽřƵźĭŻřŚƷ ƵŶƴƷŵžƿƹźſŻřĨƿźƷƲŤƟŹƽřźŝƶƴƿżƷžƿźţŚƯźĭř ƶƫŚƀƯƝŶƷƮǀƷŵƂƿŚưƳ C žƿźţŚƯŚŝƾƬĩŹƺƐŝřŹźĮƿŵƵźĭƶŝ ƽřźŝ ƶƴƿżƷ ƲƿźŤưĩ Śŝ ƽźǀƀƯ ƲŤƟŚƿ Żř Ţſř šŹŚŞƗ ƹ ŚƷƽźŤƄƯ ƽřźŝ ƵŶƃ źĩŷ Ǝƿřźƃ ƶĪƿŹƺƐŝ ŚƷƵŶƴƷŵ žƿƹźſ
ŶƳŵźĭŻŚŝŹŚŞƳřƶŝ ŵŹƺƯŹŚǀƀŝƵŻƹźƯřƱōƽŚƷƶŴƀƳƹƶƫŚƀƯƲƿřŶƃƶŤƠĭƶĩŹƺƐƳŚưƷ ŵŹƺƯƽŵŚƿŻƽŚƷƂŴŝŹŵƹƶŤƟźĭŹřźƣƱŚƤƤŰƯƹƱřŶƴưƄƳřŵƶūƺţ ƮŤƀǀſ ŵŹřƺƯ ƶŝ ƱřƺţƾƯƩŚŨƯ ŹƺƐŝ ƶĩ ŵźǀĭƾƯ Źřźƣ ƵŵŚƠŤſř
ƽźƸƃ ƽŚƷƶƫŚŝŻ ƱŵźĩƖưū ƾŤƀě šLJƺſźƯ ƪưů ƾƳřźſƺŝƺţř
ƵŹŚƃř ƹ ƶƯŚƳŻƹŹ ƖƿŻƺţ ƽŹŚŝ ƽŚƷŚưǀěřƺƷ ƹ ŚƷƾŤƄĩ ƾŝŚƿźǀƀƯ
ŵźĩ ƂŴŝŹŵřŹƶǀƬƤƳƶƬǀſƹƾŝŚƿźǀƀƯƶƫŚƀƯƩŶƯřŶŤŝřŚƯƶƫŚƤƯƲƿřŹŵ ƽŵŚƸƴƄǀě ƁƹŹ ŮǀƋƺţ ƶŝ è ƂŴŝ Źŵ žĜſ ƹ ƮǀƴĩƾƯ ƶŗřŹř ç
ƵŵřŵŮǀƋƺţřŹĨǀŤƳĥƮŤƿŹƺĮƫřƁƹŹřŶŤŝřƂŴŝƲƿřŹŵƮƿŻřŵźěƾƯ ƁƹŹ ŚƸŤƳř Źŵ ƹ Ƶŵřŵ ŭźƃ řŹ ŽŹŵƹŻ ƾƿřźĮưƷ ƭƺƸƠƯ žĜſ ƹ ŪƿŚŤƳ ƮǀƷŵƾƯ Źřźƣ ƪǀƬŰţ ƹ ƶƿżŬţ ŵŹƺƯ řŹ ŵƺų ƽŵŚƸƴƄǀě Źŵ řŹ Ţſř ƵŶƃ řźūř ŵŹřŶƳŚŤſř ƽŚƷƩŚŨƯ ƽƹŹ źŝ ƶĩ ƾţŚŞſŚŰƯ
ƹ ƽźǀĭƶŬǀŤƳ ŚƸŤƳř Źŵ ƹ Ƶŵřŵ Źřźƣ ƪǀƬŰţ ƹ ƶƿżŬţ ŵŹƺƯ é ƂŴŝ ŵŵźĭƾƯƶŗřŹřêƂŴŝŹŵƵŶƴƿōƽŚƷƽźǀĭŢƸū
ŢŴſ ƪŗŚƀƯ Ōżū ƶǀƬƤƳ ƶƬǀſƹ ƾŝŚƿźǀƀƯ ƶƫŚƀƯ ƶĪƴƿř ƮƛŹLjƗ ƾƐų ƽżƿŹƶƯŚƳźŝ ƩŶƯ Ĩƿ šŹƺƇ ƶŝ ŶƳřƺţƾƯ ŵƺƃƾƯ śƺƀŰƯ
ŚƸƳō Żř ƩŶƯ ŢųŚſ Źŵ ƶĩ ƾƿŚƷŢƯLjƗ ŵƺƃ Ƶŵřŵ ƂƿŚưƳ ŮǀŰƇ
ƦƿŢſř G ƝřźĭƽƹŹƶƴƿżƷžƿźţŚƯƵŶƴƷŵƱŚƄƳƶƧC 
cij c ji ƮƿŹřŵ (i 0,1,2,…,n; j 0,1,2,…,n)
ƶƬǀſƺŝ i Ƶźĭ(i  0,1,2,…,n;k 1,…,m) ƽřźŝźĭř 
Źŵ ƹ yik 1 ƵŚĮƳō ŵźǀĭ Źřźƣ šŚƣLjƯ ŵŹƺƯ k ƶǀƬƤƳ ƶƬǀſƹ Ţſř yik  0 šŹƺƇƲƿřźǀƛ
ƶǀƫƹř ƽŚƷśřƺū ƲŤƟŚƿ ƽřźŝ ŚƷƁƹŹ Ʋƿř Żř ƾŞǀĩźţ ƽŚƷƮŤƿŹƺĮƫř
śƺų ƽŚƷśřƺū Ʋƿř ƲŤƟŚƿ ƽřźŝ ŵƺƃƾƯ ŜŞſ ƶĩ ŵźĩ ƵŵŚƠŤſř źĭř ƽŹŚĪŤŝřřźƟ ƽŚƷƁƹŹ źĮƿŵ ƝźƏ Żř ŵƺƄƳ ƝźƈƯ ƽŵŚƿŻ ƱŚƯŻ ƶŝ ŢŞƀƳ řŹ ƽźŤƄǀŝ ƱŚƯŻ ƲǀƸŝźƿŻ ƽŚƷśřƺū ƲŤƟŚƿ ƽřźŝ ƶģ ƽřŹřŵ Ŷƃźĩŷ ƶĩ ŹƺƐƳŚưƷ ŚƯř ŶƴƴĩƾƯ ƝźƈƯƽŹŚĪŤŝřƽŚƷƁƹŹ
ƹ ŶƴŤƀƷ ƾƬŰƯ ƶƴǀƸŝ ƍŚƤƳ Żř ŹřźƟ ƽřźŝ ƾŝƺų ŹŚǀƀŝ ƽŚƷŹŚĪƷřŹ ƶĩŵźĩƶūƺţŶƿŚŝŶƴŝŚƿŢſŵƾŝƺųŹŚǀƀŝƽŚƷśřƺūƶŝŶƴƳřƺţƾƯ Źŵ śřƺū Ĩƿ ƲŤƟŚƿ ƽřźŝ ƽŵŚƿŻ ŚŤŞƀƳ ƱŚƯŻ ƽŚƷƮŤƿŹƺĮƫř Ʋƿř Źŵ ƲƿřźŝŚƴŝ ŵƺƃƾƯ ƝźƈƯ ƽŹŚĪŤŝř ƽŚƷƮŤƿŹƺĮƫř ƽŚƷśřƺū Ŷů ŵƺŞƸŝƽřźŝŚƷƁƹŹƲƿřŻřƾŞǀĩźţƽŚƷƮŤƿŹƺĮƫřŻřƾƌƘŝŹŵƱřƺţƾƯ ƾŝƺųŹŚǀƀŝƽŚƷśřƺūŜǀţźţƲƿŶŝƹŵźĩƵŵŚƠŤſřƶǀƫƹřƽŚƷśřƺū ŶƿōƾƯ ŢſŶŝ ƽŹŚĪŤŝřřźƟ ƽŚƷƮŤƿŹƺĮƫř ƶŝ ŢŞƀƳ ƽźŤưĩ ƱŚƯŻ Źŵ
ŵƺųƶŝřŹƽŵŚƿŻŹŚǀƀŝƶūƺţƵŻƹźƯřƶĩŚƷƮŤƿŹƺĮƫřƲƿřŻřƶƳƺưƳƽřźŝ ŚƷƶŤƃŹŻřƽŹŚǀƀŝŹŵřŹŚƷƁƹŹŻřƶƳƺĮƴƿřƱřŶƴưƄƳřŵƹƵŵźĩśŸū ƹ ĨǀŤƳĥ ƾŞǀĩźţ ƽŚƷƮŤƿŹƺĮƫř ƶŝ ƱřƺţƾƯ ŶƳźŝƾƯ ŹŚĪŝ ÎƾƘưū ƲƿźŤĪƿŵżƳ ƮŤƿŹƺĮƫř ƹ ĨǀŤƳĥ ƹ śƹŹŚū >æí@ƱŚĭŶƳźě ƽƺŬŤƀū ƮŤƿŹƺĮƫř >çå@ƱŚĮģŹƺƯ ƹ ÏƵŶƴĩřźě ƮŤƿŹƺĮƫř >æî@
ƽŻŚſƶǀŞƃ ƹ ƱŚĭŶƳźě ƁƹŹ ƹ >çæ@ƾƬǀƳō ƽŻŚſƶǀŞƃ ƹ ƕƺƴưƯ
ŻřƾĪƿƶƫŚƀƯƲƿřŢſřƵŶƃŜŞſƶĩƾƬƯřƺƗŻřƾĪƿźĮƿŵƝźƏŻř Żř ƽŹŚǀƀŝ ƶūƺţ ƹ ŵźǀĭ ŜƤƫ ƾţŚŞǀĩźţ ƽŻŚſƶƴǀƸŝ ƮƸƯ ƪŗŚƀƯ
ƶƳŚųŹŚĩ Ĩƿ ƶĩ Ŷǀƴĩ ƉźƟ ƩŚŨƯ ŹƺƐŝ Ţſř ƾƘƣřƹ ƽŚǀƳŵ Źŵ Ʊō ƪƿŚſƹ ŵřŶƘţ Śƿ ƹ ƱŚƿźŤƄƯ ƶŝ LJŚĩ ƪƿƺŰţ źǀƀƯ ƩƺƏ ŶƃŚŝ ŹŵŚƣ ƂƷŚĩŚŝƲƿřźŝŚƴŝŶƷŵƂƷŚĩřŹŵƺųƶƴƿżƷƶŬǀŤƳŹŵƹŵƺųƶǀƬƤƳ ŢƗźſƂƿřżƟřŚŝŶƳřƺţƾƯŢĩźƃLJŚĩŚŤƟŚƿŹŵŚƿƪƿƺŰţźǀƀƯƩƺƏ
źŝƹƵŵřŵƶŗřŹřƂƳŚƿźŤƄƯƶŝřŹƽźŤƸŝšŚƯŶųŵƺųƽLJŚĩƪƿƺŰţŹŵ ŢŝŚƣŹšŹŶƣƶƏƺŝźƯŢĩźƃƶŬǀŤƳŹŵŶƿřżƠǀŝŵƺųƱŚƿźŤƄƯŵřŶƘţ ƽLJŚĩŹřŻŚŝƹƵŵřŵƂƿřżƟřźĮƿŵƶŝŚƄƯƽŚƷŢĩźƃƪŝŚƤƯŹŵřŹŵƺų
ŶƷřƺųŜƀĩřŹƽźŤƄǀŝŵƺſŢƿŚƸƳŹŵƹŶƷŵƾƯƁźŤƀĭřŹŵƺų Ɩǀſřƺţ ƽřŹřŵ ƶƫŚƀƯ Ʋƿř Ŷƃ ƶŤƠĭ ƶĩ ŹƺƐƳŚưƷ ƶģ źĭř ŵźĩ
ƶƫŚƀƯ ĨǀſLjĩ ƕƺƳ ƶŝ ŚƯ ƶƫŚƤƯ Ʋƿř Źŵ ŚƯř Ţſř ƾƳƺĭŚƳƺĭ
ŵƺƃƾƯƞƿźƘţźƿŻšŹƺƈŝƶĩƮƿŻřŵźěƾƯ Ʊō Źŵ ƶĩ ŶƃŚŝ ƾƟřźĭ ƵŶƴƷŵ ƱŚƄƳ GV( ,A) ƶĩ Ŷǀƴĩ ƉźƟ
ƹƵźĭn1ƵŶƴƷŵƱŚƄƳ V  {0,1,…, n}
ƽŚƷƩŚƿ ƶƗƺưŬƯ ƵŶƴƷŵ ƱŚƄƳ A{(i, j)|i, jV andi  j} żū ƶŝ ŚƷƵźĭ Żř Ĩƿ źƷ ƶƫŚƀƯ Ʋƿř Źŵ ŶƃŚŝ G Ɲřźĭ Źŵ ŵƺūƺƯ ƽŚƋŚƤţ ŹřŶƤƯ ƽřŹřŵ ƹ Ƶŵƺŝ ŚƷƽźŤƄƯ ƵŶƴƷŵ ƂƿŚưƳ 0 Ƶźĭ

nearest addition algorithm
Scatter search
Ʋƿř ŵƺƃƾƯ śƺƀŰƯ ƾưƸƯ ŹŚǀƀŝ ŢƿŵƹŶŰƯ ƭƺſ ŢƿŵƹŶŰƯ
ŶƴŞưƷ ƶĩ ƾŝřƺū ŵŚŬƿř Żř ƮŤƿŹƺĮƫř ƶĩ ŵƺƃƾƯ ŜŞſ ŢƿŵƹŶŰƯ ç ƪĪƃ Źŵ ƶĩ ŹƺƐƳŚưƷ źĮƿŵ šŹŚŞƗ ƶŝ ŶƴƧ ƽźǀĭƺƬū ŶƃŚŞƳ
źǀƛƶŝƵźĭźƷƶŝƹƵŵźĩơŶƇçƹæƎƿřźƃŹŵƩŚŨƯƲƿřŶǀƴǀŝƾƯ ŵřŶƘţƲƿřƲǀƴĤưƷƹŵŵźĭƾƯũŹŚųƩŚƿĨƿƹŵŹřƹƩŚƿĨƿŹŚŞƳřŻř źǀƛśřƺūĨƿƶĪǀƫŚůŹŵŢſřmŹŚŞƳřƽřźŝƾūƹźųƹƽŵƹŹƹƩŚƿ ƾſźŤſŵLJŚĩŹŚŞƳřƶŝæéƹæèéƵźĭƶſřźƿŻŶƃŚŝƾƯƩƺŞƣƪŝŚƣ ƶĩŵƺƃƾƯŜŞſLJŚŝŢƿŵƹŶŰƯçƵřźưƷŢƿŵƹŶŰƯƲƿřžěŶƳŹřŶƳ ŹřźƣšŚƣLjƯŵŹƺƯŹŚŞĪƿŚƤǀƣŵƹƶŤƃřŶƳƾƬĪƄƯƶūŹŵźƔƳŻřŚƷƵźĭ
ŶƴĩƾƯƽźǀĭƺƬūŹŚŞƳřƶŝƪƈŤƯŚƳŹƺţźƿŻŵŚŬƿř ƪŗŚſƹŻřƭřŶĩĢǀƷƶĩŶƴĩƾƯƵŹŚƃřƶŤĪƳƲƿřƶŝƭŹŚƸģŢƿŵƹŶŰƯ
ƶŝ ƭřŶƣř Q ŢŝŚŧ ŢǀƟźƓ Żř źŤƄǀŝ ƶĩ ŵƺŝ ŶƴƷřƺŴƳ ŻŚŬƯ ƶǀƬƤƳ
ŶƴƧƾƯƵŹŚƃř yik ƹ x ij
ŵƺƃƾƯƪƿŶŞţ ƾŝŚƿźǀƀƯ ƶƫŚƀƯ ƽřźŝ ƩƺŞƣ ƪŝŚƣ śřƺū Ĩƿ è ƪĪƃ ƩŚŨƯ ŹƺƐŝ ç ƪĪƃ ŶƴƳŚưƷ ƶƫŚƀƯ Ʋƿř Źŵ ŶƷŵƾƯ ƂƿŚưƳ řŹ ƶǀƬƤƳ ƶƬǀſƹ ƪĪƃŹŵƶĩƽŹƺƐƳŚưƷŢſřƵŶƃƶŤƟźĭźƔƳŹŵn=çåƹm=ê

ƶǀƬƤƳƶƬǀſƹƾŝŚƿźǀƀƯƶƫŚƀƯĨƿƪůŻřƽřƶƳƺưƳè ƪĪƃ
Źŵ ŹƺƔƴƯ ƲƿŶŝ ŵƺƃƾƯ ŭźƐƯ ƽŵŚƸƴƄǀě ƮŤƿŹƺĮƫř ƂŴŝ Ʋƿř Źŵ Ʋƿř ƹ ƵŶƃ ŭźƐƯ ĨǀŤƳĥ ƮŤƿŹƺĮƫř źŝ ƽřƶƯŶƤƯ řŶŤŝř æ ƂŴŝ źƿŻ ƭƺƸƠƯ ç ƂŴŝ źƿŻ Źŵ žĜſ ŵźǀĭƾƯ Źřźƣ ƶūƺţ ŵŹƺƯ ƮŤƿŹƺĮƫř ĨǀŤƳĥ ƮŤƿŹƺĮƫř ŵŹƺƯ Źŵ řźƳō ƹ ƵŶƃ ƾƟźƘƯ ŽŹŵƹŻ ƾƿřźĮưƷ
ŭźƃ řŹ ƽŵŚƸƴƄǀě ƮŤƿŹƺĮƫř ƶſ ƂŴŝźƿŻ Źŵ ŚŤƿŚƸƳ ƹ Ƶŵřŵ ŮǀƋƺţ ƮǀƷŵƾƯŹřźƣƾſŹźŝŵŹƺƯźŤƄǀŝšŚǀŗżūŚŝřźƳōƹƵŵřŵ ŹƺƏƶŝƶǀƬƤƳƶƬǀſƹ (i, j  0,1,2,…,n;i  j) ƽřźŝźĭř  šŹƺƇƲƿřźǀƛŹŵƹ x ij 1 ŶƴƧŢƧźů j ƶŝ i ŻřƮǀƤŤƀƯ
ŶƃŚŝƾƯ x ij  0
ƽŶƴŝƩƺƯźƟŽŚſřźŝƶĩƶǀƬƤƳƶƬǀſƹƾŝŚƿźǀƀƯƶƫŚƀƯƩŶƯƲƿřźŝŚƴŝ ŻřŢſřšŹŚŞƗŶƃŚŝƾƯ>çè@ŵźĭƵŹƹŵƵŶƴƃƹźƟƲƿŶƴģƶƫŚƀƯ
iŖ jŖ æ
xij 
iŖm j  ŗǰǯǯǯǰn
çj  Ŗ
xij 
jŖm i  ŗǰǯǯǯǰn
i  Ŗè


i,jS xij  Sŗ ǻS ǿŗǰǯǯǯǰnȀǰ S  ŘǼ é
qiyik QǻkŗǰǯǯǯǰmǼ ê
xij ǿŖǰŗȀǻi  ŖǰǯǯǯǰnDz j  ŖǰǯǯǯǰnǼ ë
yik ǿŖǰŗȀǻiŖǰǯǯǯǰnDzkŗǰǯǯǯǰmǼì
ũŹŚų ƩŚƿ m ŹŚŞƳř Ƶźĭ Żř ƶĪǀƫŚů Źŵ ŵƺƃƾƯ ũŹŚų ƩŚƿ Ʀƿ

ƾŝŚƿźǀƀƯƶƫŚƀƯƩƺŞƣƪŝŚƣźǀƛƪůĨƿŻřƽřƶƳƺưƳç ƪĪƃ ƶǀƬƤƳƶƬǀſƹ

ĨƿƽřŹřŵƾƟŵŚƈţšŹƺƈŝŚƷśřƺūƽƺŬŤƀūŚƷƞƘƋƲƿřƮƛŹƾƬƗ ƮŤƿŹƺĮƫřƶĩŵŵźĭƾƯŜŞſƪưƗƲƿřƭŚŬƳřŶƃŚŝƾƯżǀƳźĮƿŵŢƿżƯ ƹ Ñ ƪĪƃ ƾƬŰƯ ƶƴǀƸŝ ƍŚƤƳ Żř ŹřźƟ ƽřźŝ ƾŞſŚƴƯ ŹŚĪƷřŹ ƽřŹřŵ
ƶŝĨǀŤƳĥƁƹŹƾƬĩƮŤƿŹƺĮƫřŵƺƃƽźſřźſƶƴǀƸŝƶŝƱŶƃĨƿŵżƳ ƾƳŶƃ ƽŚƷśřƺū ƭƹŻƺƯƹźĩ ƽŵřŶƘţ ƽřźŝ řŶŤŝř ƶĩ Ţſř ƩřƹŹ Ʋƿř
ŵƺƃƾƯƵŵŹƹōŢſŶŝƝŶƷƖŝŚţźƿŵŚƤƯ ƶǀƫƹř ŢǀƘưū ŚůLjƐƇř ƶǀƫƹř ƾƳŶƃ ƽŚƷśřƺū Żř ƶƗƺưŬƯ Ʋƿř
ŻřƭřŶĩźƷƝŶƷƖŝŚţźƿŵŚƤƯŽŚſřźŝƭƹŵƶƬůźƯŹŵŵƺƃƾƯƵŶǀƯŚƳ ƽźŤƸŝ źƿŵŚƤƯ ƽřŹřŵ ƶĩ řŹ ŚƸƳō Żř ƽŵřŶƘţ ƾƳŶƃ ƽŚƷśřƺū ŵƺūƹ ƶĩ ƾƳƺĭŚƳƺĭ ƽŚƷŢƫŚů ŽŚſřźŝ ƹ Ƶŵźĩ śŚŴŤƳř ŶƴƃŚŝƾƯ ƽŶƿŶūƽŚƷŢǀƘưūƹŶƳƺƃƾƯŜǀĩźţźĮƿŶĪƿŚŝŚƷŶƫřƹƲƿřŵŹřŵ ƽŶƘŝŹřźĪţŹŵƶǀƫƹřƽŚƷŢǀƘưūƶĩŵźĩƶūƺţŶƿŚŝŶƴƿōƾƯŵƺūƺŝ ƾƟŵŚƈţ ŢǀƘưū ƽŵřŶƘţ Żř ƖƣřƺƯ ƾƌƘŝ Źŵ ƹ ŚƷŶƳŻźƟ ŚƷŶƫřƹ Żř ƲƿżĮƿŚū ŶƿŶū ƽŚƷŢǀƘưū Ʋƿř ŢƿŚƸƳ Źŵ Ţſř ƵŶƃ ƪǀĪƄţ
ƶƯřŵř ƾƿŚū Śţ ƪưƗ Ʋƿř ŶƳƺƃƾƯ ƾƬŞƣ ƽŚƷŢǀƘưū Żř ƽŵřŶƘţ ƶŝƮŤƿŹƺĮƫřƽřźūřƱŚƯŻŶƴƳŚƯƾƿřźĮưƷƽŚƷŹŚǀƘƯŻřƾĪƿƶĩŶŝŚƿƾƯ
ƱŶƃ ŹřźĪţ ƹ ƵŶƃ ƲǀǀƘţ Ƃǀě Żř ƽŚƸƬƀƳ ŵřŶƘţ ŢŝŚŧ ƽŹřŶƤƯ

ƽźſřźſƹƾƬŰƯƶƴǀƸŝé ƪĪƃ
ŹƺƐŝ ƺŬŤƀū Ʊō ƽƶƐſřƹ ƶŝ ƶƧ ŢƀƿřƵŶƿŶě ŽŹŵƹŻ ƾƿřźĮưƷ ŹŵƺŬŤƀūƹƵŶƃřźĮưƷƾƳŶƃƽŚƌƟŻřƾƇŚųƶǀůŚƳƶŝƭŚĮƴƷŵƹŻ ƮŤƿŹƺĮƫř ƶŬǀŤƳ Źŵ ŵƺƃƾƯ żƧźưŤƯ ƾƬŰƯ ƽŚƷƶƴǀƸŝ ƝřźƏř ƾƿřźĮưƷ źĮƿŵ šŹŚŞƗ ƶŝ ŶŝŚƿ Ţſŵ ƽźſřźſ ƶƴǀƸŝ ƶŝ ŶƳřƺţƾưƳ ƶŝ ƾƟŚĩ Ŷů Śţ ƶĪƴƿř ƱƹŶŝ ƮŤƿŹƺĮƫř ƶĩ ŵƺƃƾƯ ŜŞſ ŽŹŵƹŻ ƽŚƌƟ ƪĩ ƾƫƺŞƣ ƪŝŚƣ Ŷů Śţ ŶƳřƺŤŝ ƹ ŵŻřŵźĜŝ ƽźſřźſ ƽƺŬŤƀū
ŚƷśřƺū Żř ƶƤƐƴƯ Ĩƿ ƽƺſ ƶŝ ŶƷŵ Źřźƣ ƾſŹźŝ ŵŹƺƯ řŹ śřƺū
ŶƷŵŹřźƣƾſŹźŝŵŹƺƯřŹśřƺūƲƿřƽŚƷƾĮƿŚƀưƷƹƵŵźĩŢĩźů ƽŚƌƟƽŚƷśřƺūŻřƾƸūƺţƪŝŚƣŢưƀƣƶĩŵƺƃƾƯŜūƺƯźƯřƲƿř ŶƿōŶƿŶěƺŬŤƀūŽŹŵƹŻŵƺƧŹƹŵźǀĮƳŹřźƣƾſŹźŝŵŹƺƯƶƳƺưƳ
ƶĩŵƺƃƾƯŜŞſƶŤſřƺųŚƳŵƺĩŹƲƿřĨǀŤƳĥƮŤƿŹƺĮƫřŹŵƩŚŨƯŹƺƐŝ ƽŚƷƪů ƵřŹ ƹ ŵŹƹō ŢſŶŝ řŹźĪƯ řŹ ƾƸŝŚƄƯ ƽŚƷśřƺū ƮŤƿŹƺĮƫř ĨǀŤƳĥƮŤƿŹƺĮƫřèæ
ƶĩŢſřƽŹŚĪŤŝřřźƟƽŚƷƁƹŹƲƿźţŹƺƸƄƯŻřƾĪƿĨǀŤƳĥƮŤƿŹƺĮƫř Ŷƃ ƕřŶŝř >çé@ æîìê ƩŚſ Źŵ ƂƳřŹŚĪưƷ ƹ ÎŶƴƫŚƷ ƱŚū Ǝſƺţ æîíî ÏīźŝŶƬĭ ŶƴƳŚƯ ƽźĮƿŵƱřŶƴưƄƳřŵ ƶƬǀſƺŝ ƁƹŹ Ʋƿř ŚƷŶƘŝ
Żř ƾĪƿ ƶŝ ƵŻƹźƯř ƹ Ƶŵźĩ řŶǀě ƶƘſƺţ >çì çë@ƲƿźƿŚſ ƹ >çê@ ƽŻŚſƶƴǀƸŝ ƪŗŚƀƯ ƪů ƽřźŝ ƾƴǀưŴţ ƽŚƷƁƹŹ ƲƿźţŵźŝŹŚĩźě
Ʋƿř Żř ƽŵŚƿŻ ƱŚƤƤŰƯ ƹ ƱřŶƴưƄƳřŵ ƹ Ţſř ƵŶƃ ƪƿŶŞţ ƾţŚŞǀĩźţ ŻřŶƳřƶŤƀƳřƺţƹƵŵźĩƵŵŚƠŤſřŵƺųŻŚǀƳŵŹƺƯƪŗŚƀƯƪůƽřźŝƁƹŹ ƽŹŚĪŤŝřřźƟƽŚƷƁƹŹźƿŚſŚŝƶƀƿŚƤƯŹŵƁƹŹƲƿřƱŵƺŝźƿŸěƝŚƐƘƳř
ƪŗŚƀƯ ƪů ƽřźŝ ƽƺƣ ƺŬŤƀū ĨǀƴĪţ Ĩƿ ƶĩ ƮŤƿŹƺĮƫř Ʋƿř ŵƺƃƾƯ śƺƀŰƯ ƶƴǀƸŝ ƪů ƵřŹ ƲŤƟŚƿ ƹ ƾţŚŞǀĩźţ ƽŻŚſƶƴǀƸŝ ƵŶƃƶŤƟźĭƭŚƸƫřŢƘǀŞƏŻřƱŚĭŶƳźěƹƱŚĮģŹƺƯƽŚƷƁƹŹŶƴƳŚưƷ ŢŧřŹƹ ŶƴƳŚƯ ƾƿŚƷźŤƯřŹŚě ƾſŚƴƃ ŢƀƿŻ ƮƬƗ ƱƺĤưƷ ƹ Ţſř ŵŚŬƿřƽřźŝƱŚƯŻƩƺƏŹŵƩŚůƲƿřŚŝŵŹřŵŜǀĩźţƹśŚŴŤƳřƂƸū ƽŚƷƶŴƀƳ ƹ ƶŤƟźĭ Źřźƣ ƾſŹźŝ ŵŹƺƯ ƮŤƿŹƺĮƫř Ʋƿř źţřŹŚĩ ƮŤƿŹƺĮƫř ƱŚĪƯ ƁƹŹ Ʋƿř ƶŬǀŤƳ Źŵ Ţſř ƵŶƃ ŵŚŬƿř ƮŤƿŹƺĮƫř Żř ƽźŤƿƺƣ ƾƃƹŹ ƶŝ żǀƳ ƵŻƹźƯř ƹ ƶŤƟŚƿ ƾţŚŞǀĩźţ ƽŻŚſƶƴǀƸŝ Źŵ řŹ Ƃƿƺų
ƽřźŝ ƱŚĮģŹƺƯ ƹ ƱŚĭŶƳźě ƽŚƷƁƹŹ ƶǀŞƃ ƶĩ ƁƹŹ Ʋƿř ƲǀƴĤưƷ ŻřŶƴĩƾƯƵŵŚƠŤſřƽřƶƬƯŚƗŶƴģƽŚƷƮŤƀǀſŻřśřƺūƶŝƱŶǀſŹ ƽŹŚǀƀŝŹŵƹƵŵƺŝƢƟƺƯŹŚǀƀŝƪŗŚƀƯŹŵƽźƿŸěƮǀưƘţŢǀƬŝŚƣźƔƳ ƮŤƿŹƺĮƫřƶĪƴƿřƶŝƶūƺţŚŝƪŗŚƀƯƲƿřŹŵŵƺƃƾƯźƷŚƓŚƷŵźŝŹŚĩŻř ŵŚŬƿř Śŝ ŶƳřƺţƾƯ ŵŹřŶƳ ƍƺŝźƯ ƶƫŚƀƯ ŵŹƺƯ Źŵ ƾţŚƗLjƏř ĢǀƷ ƹƵŵźĩŢĩźůźŤƸŝƽŚƷśřƺūƲŤƟŚƿźǀƀƯŹŵƾƟŵŚƈţƽŚƷśřƺū ƶūƺţŶƿŚŝŶƿŚưƳƽƹźƄǀěƾŝƺųƶŝƱŚĪƯřŶůŚţƺŬŤƀūƽŚƌƟŹŵ Żř Ŝǀĩźţ ƹ ƂƸū śŚŴŤƳř ƽŚƷƽĦţřźŤſř ƁƹŹ Ʋƿř Źŵ ƶĩ ŵźĩ
ŢƗźſ Źŵ ŚƸƳō Żř ƭřŶĩ źƷ ƕƺƳ ƹ Ƶŵƺŝ ŹřŵŹƺųźŝ ƽŵŚƿŻ ŢǀưƷř
ŢſřŹřŵŹƺųźŝƽŵŚƿŻŢǀưƷřŻřźƔƳŵŹƺƯśřƺūƶŝƱŶǀſŹ ŵƺƃƾƯŜŞſĨǀŤƳĥƮŤƿŹƺĮƫřƾƟŵŚƈţƽƺŬŤƀūƶģźĭřƲǀƴĤưƷ ƽřŹřŵƮŤƿŹƺĮƫřƹŵźǀĭŹřźƣƾſŹźŝŵŹƺƯƾŝƺųƶŝƶƫŚƀƯƽŚƌƟƶĩ řŹřŵƾƫƹŶƃŚŝźţŢǀƠǀĩŚŝƽŚƷśřƺūƶŝƱŶǀſŹƽřźŝřŹŚĩŹŚĪƷřŹĨƿ ƲǀƸŝśřƺūƶŝƱŶǀſŹŢƗźſƶĩŵƺƃƾƯŜŞſŹŚŤųŚſƲƿřƱŵƺŝ
ƽƺŬŤƀū źĮƿŵ ƝźƏ Żř ŶŝŚƿ ƂƷŚĩ ƽŹŚĪŤŝř ƽŚƷƁƹŹ ƶŝ ŢŞƀƳ ƽřźŝƾƟŚĩƽŹřŶƿŚěĨƿŻřƮŤƿŹƺĮƫřƲƿřƶĩŵƺƃƾƯŜŞſƾƟŵŚƈţ
ƮŤƿŹƺĮƫř ŹźĪƯ ƽŚƷřźūř ƹ ƵŵƺŞƳ ŹřŵŹƺųźŝ ƶƴǀƸŝ śřƺū ƶŝ ƱŶǀſŹ ŵƺƃšƹŚƠŤƯƽŚƷśřƺūƱŶƯōŢſŶŝŜŞſ

ԝҝÎѝѝÓƽźŤƄƯƂƃƩƹřƶǀƬƤƳƶƬǀſƹƶƬǀſƺŝÎÍƹϝÎÎ ƶƬǀſƺŝ Õ ƹ ÎÐ Ö ƽźŤƄƯ ƶſ ƹ ƭƹŵ ƶǀƬƤƳ ƶƬǀſƹ ƶƬǀſƺŝ ÎÏ ƹ
Ʋƿř źĮƿŵ ƝźƏ Żř ŶƳźǀĭƾƯ Źřźƣ šŚƣLjƯ ŵŹƺƯ ƭƺſ ƶǀƬƤƳ ƶƬǀſƹ
ŻřźŤưĩƶǀƬƤƳƶƬǀſƹƶſŹŚŝƶĩŶƃŚŝƾƯƩƺŞƣŵŹƺƯƾţŹƺƇŹŵśřƺū ƭƹŻƺƯƹźĩƩƹřƂŴŝƽƹŹźŝšŚǀƬưƗƽŵŚƸƴƄǀěƁƹŹŹŵŶƃŚŝQ
ÓƪĪƃƽřƶƐƤƳĨţƁƹŹžĪƗźŝƹŵźǀĭƾƯšŹƺƇƵŶƃƞǀƇƺţ ƭƹŻƺƯƹźĩŻřƾƟŵŚƈţƱĥmƁƹŹƲƿřŹŵŵŹřŶƳŵƺūƹƾŤƀĪƃƶƐƤƳ ŢſŶŝźƓŚƴŤƯƭƹŻƺƯƹźĩŜǀţźţŽŚſřźŝřźƳōƹƵŶƃśŚŴŤƳřƶƏƺŝźƯ
Źŵ ƩŚŨƯ ŹƺƐŝ ŵƺƃƾƯ ƲƿżĮƿŚū źƔƳ ŵŹƺƯ ƭƹŻƺƯƹźĩ Źŵ ƹ ƵŵŹƹō
Źŵ źĭř ƪĪƃ Ʋƿř Źŵ Ţſř ƵŶƃ Ƶŵřŵ ŮǀƋƺţ ƁƹŹ Ʋƿř Ô ƪĪƃ źƔƳŹŵƾƟŵŚƈţƱĥÑƱřƺƴƗƶŝřŹÑƹҝΝÏŵřŶƗřÎƭƹŻƺƯƹźĩ
ƭƹŻƺƯƹźĩŹŵƶĩƾŞǀţźţƶŝźƈƴƗŹŚƸģƲƿřŶƿŚŝƵŚĮƳōŵƺƃƶŤƟźĭ ÏÑÎŚŝŢſřźŝřźŝŜǀţźţƲƿřƶĩŵƺƃƲƿżĮƿŚūŵŹřŵŹřźƣźƓŚƴŤƯ ÐÑÓÏÒƭƹŻƺƯƹźĩƶŝƪƿŶŞţÏÐÎÓÒÑƭƹŻƺƯźĩƲƿřźŝŚƴŝÒƹ ŢƫŚůĨƿŶƿŶūŜǀĩźţŶǀƴĩƾƯƵŶƷŚƄƯƶĩƽŹƺƐƳŚưƷŵƺƃƾƯÎ ƽźŤƄǀŝŢƿżƯƽřŹřŵƶĩŶƷŵƾƯƱŚƄƳřŹƾƬŞƣƁƹŹŻřźţƵŵźŤƀĭ ƱŚƄƳƽźŤƄǀŝšŚǀŗżūŚŝÒƂŴŝŹŵƶĩƵŵƺŝƾưƿŶƣƁƹŹƶŝŢŞƀƳ Śŝ śřƺū ƽŚƌƟ ƶĩ ŵƺƃƾƯ ŜŞſ ƁƹŹ Ʋƿř ƲƿřźŝŚƴŝ ŵƺƃƾƯ Ƶŵřŵ ƽźţżƿŚưŤƯƾƿŚƷśřƺūƹŵƺƃƶŤƠĭŹřźƣƾſŹźŝŵŹƺƯƽźŤƄǀŝŢǀƠǀĩ ƶŝŢŞƀƳƁƹŹƲƿřŹŵƵŶƯōŢſŶŝƽŚƷśřƺūƶŬǀŤƳŹŵŵŵźĭŶǀƫƺţ ƮŤƿŹƺĮƫřƲƿřŹŵƲǀƴĤưƷŶƃŚŝƾƯƽźŤƸŝźƿŵŚƤƯƽřŹřŵƾƬŞƣƁƹŹ ŚƷśřƺūŢǀƠǀĩźŤƄǀŝƱŵźŝLJŚŝƽřźŝíƪĪƃƂƸūƁƹŹƹŵŻř
ƊƿƺƘţƹƱĥƹŵśŚŴŤƳřŻřŢſřšŹŚŞƗƾĪƿƶĩŢſřƵŶƃƵŵŚƠŤſř ƭƹŵŢưƀƣŹŵƱĥƹŵśŚŴŤƳřƽźĮƿŵƹƭƹŻƺƯƹźĩƩƹřƂŴŝŹŵƱō ŻřřŹèƹêźĭříƪĪƃŹŵƩŚŨƯŹƺƐŝŚƸƳōƾƿŚŬŝŚūƹƭƹŻƺƯƹźĩ èêëƶŝƭƹŻƺƯƹźĩƭƹŵŢưƀƣƵŚĮƳōƮƿźǀĮŝźƔƳŹŵƭƹŵŢưƀƣ ŚƷƂƸūƲƿřƹŵźƷŹřźĪţźƷŹŵƶĩŵźĩƶūƺţŶƿŚŝŵƺƃƾƯƪƿŶŞţ ŻřƵŵŚƠŤſřŚŝƪưƗƹŵƲƿřŻřƾĪƿƶĪƬŝŵźǀĭƾưƳŹřźƣƵŵŚƠŤſřŵŹƺƯ ƽŵŚƿŻ ƾưƬƗ ƱƺŤƯ ƵƹLjƗ ƶŝ ŵƺƃƾƯ śŚŴŤƳř ƾƟŵŚƈţ ƁƹŹ Ĩƿ ƽřźŝśƺųŢƟŚǀƷŹƦƿƶƧŶƴƴƧƾƯƱŚǀŝƾƴǀưŴţƽŚƷƁƹŹŵŹƺƯŹŵ
ŚŝƶƏƺŝźƯƮŤƿŹƺĮƫřŜǀƧźţLJŚŝŢǀƠǀƧŚŝƽŚƷƪůƵřŹƶŝƾŝŚǀŤſŵ ŹŵŢſřźŤƸŝƽŚƷƪůƵřŹŶǀƫƺţƽřźŝƾƬŰƯƽƺŬŤƀūƮƀǀƳŚƨƯƦƿ ŵƺūƹ ŹŚĩ Ʋƿř ƽřźŝ ƽŵŚƿŻ ƾƬŰƯ ƽƺŬŤƀū ƽŚƷƮŤƿŹƺĮƫř ƶĪǀƫŚů ƾŝŚǀŤſŵƽřźŝŶƴŤƀƷƾţƺƣƹƞƘƋƍŚƤƳƽřŹřŵƭřŶĩźƷƶĩŶƳŹřŵ ƮŤƿŹƺĮƫřƽŻŚſƵŵŚǀěŹŵƮŤƿŹƺĮƫřƾƿřŹŚƧŹŵźŤƄǀŝƶģźƷŵƺŞƸŝƶŝ
ŜǀƧźţƶƳŚĭƶſƵŶƴƷŵŵƺŞƸŝƾƬŰƯƽƺŬŤƀūŚŝƶƫŚƤƯƲƿřŹŵĨǀŤƳĥ ƽƹŹ źŝ ƾŤůřźŝ ƹ Ƶŵƺŝ ƵŵŚſ ŹŚǀƀŝ ƮŤƿŹƺĮƫř Ʋƿř řźƿŻ Ţſř ƵŶƃ ÖƪĪƃŹŵƶĩŹƺƐƳŚưƷƁƹŹƲƿřŵƺƃƾƯřźūřźƔƳŵŹƺƯƮŤƿŹƺĮƫř ŻřƶƿŚƀưƷźǀƛƩŚƿƶſƱŵźƧƝŸůŽŚſřźŝŢſřƵŶƃƵŵřŵƱŚƄƳ
ŶƴĩƾƯŹŚĩźĮƿŵƾƤƿźƏŻřƩŚƿƶſƱōƱŵźƧƪƈŤƯƵŹŚŝƹŵƹŹƺţ ŹƺţƵŹŚŝƹŵƱŵźƧŵŚŬƿřƹźǀƀƯƱŵźƧƪƈŤƯƽřźŝƶƧŵźƧƶūƺţŶƿŚŝ Źŵ ƶĩ ƮƿźƿŸěƾƯ řŹ ƾŤƫŚů ƎƤƟ ŚƯ ŚƯř ŵŹřŵ ŵƺūƹ ƵřŹ ƲƿŶƴģ ƾƿřŹŚĩƮŤƿŹƺĮƫřšŹƺƇƲƿřŹŵŵŻŚƀŝŹŚŝƲǀƯŶƴģƽřźŝřŹƾƸŝŚƄƯ źĮƿŵƹƵŵřŵŢſŵŻřƽŹřźĪţźǀƛƽŚƷƭƹŻƺƯƹźĩƲŤƟŚƿƽřźŝřŹŵƺų ŹŵƮŤƿŹƺĮƫřźĮƿŵšŹŚŞƗƶŝŶƴĩŶǀƫƺţƽźŤƸŝƽŚƷƪůƵřŹŶƳřƺţƾưƳ ƶƴǀƸŝ Ĩƿ ƽŚƷƾĮƿŚƀưƷ Ʊƺģ ƹ ƵŵŚŤƟř ƭřŵ ƶŝ ƾƬŰƯ ƶƴǀƸŝ Ĩƿ řźƳōƮŤƿŹƺĮƫřŢſřŹřŶƤƯƲƿřŻřƽźţŢǀƠǀĩƾŝźƿŵŚƤƯƽřŹřŵƾƬŰƯ ƲŤƟŚƿ ƽřźŝ ƁLjţ ƹ ƶŤƟźĭ źƔƳ Źŵ ƽźſřźſ ƶƴǀƸŝ ƱřƺƴƗ ƶŝ ƽŚƷśřƺūƶŝƮŤƿŹƺĮƫřƲƿřźŝŚƴŝŵƺƃƾƯƞƣƺŤƯźţŶƿŶūƽŚƷśřƺū
ƮŤƿŹƺĮƫř Źŵ ƪĪƄƯ Ʋƿř ƪů ƽřźŝ ƱřƺţƾƯ ƶĩ ƾƿŚƷƁƹŹ Żř ƾĪƿ źƷŹŵƾƟŵŚƈţƽŚƷƭƹŻƺƯƹźĩŻřƵŵŚƠŤſřŵźĩƵŵŚƠŤſřƱōŻřĨǀŤƳĥ ŹřźĪţźƷŹŵŚƷƭƹŻƺƯƹźĩƕƺƴţƶĩŵƺƃƾƯŜŞſƵŶƿřƲƿřŢſřŹřźĪţ ƩŚưŤůř Śŝ ƮŤƿŹƺĮƫř ƢƿźƏ ƲƿŶŝ ƹ Ƶŵƺŝ ŜſŚƴƯ ŹřŶƤƯ ƶŝ ƮŤƿŹƺĮƫř ƽřŹřŵ ƮŤƿŹƺĮƫř ƲƿřźŝŚƴŝ Ŷſźŝ ƶŝŚƄƯ ƽŚƷśřƺū ƶŝ ƽźŤưĩ ƹ Ƶŵƺŝ ƽŹřźĪţ źǀƛ ƽŚƷśřƺū Ŷǀƫƺţ ƽřźŝ ƽźŤƄǀŝ ƽŚƷŹŚĪƷřŹ šŹŚŞƘŝŶƴĩŶǀƫƺţźţŢǀƠǀĩŚŝƽŚƷśřƺūƽźŤƄǀŝƩŚưŤůřŚŝŶƳřƺţƾƯ Źŵ řźƿŻ ŵƺƃƾƯ ƮŤƿŹƺĮƫř ƾƿřŹŚƧ ƂƿřżƟř ŦƗŚŝ ƪưƗ Ʋƿř źĮƿŵ ŚƷƁLjţƹŢſřƵŵŚŤƟřźǀĭƾƬŰƯƶƴǀƸŝƦƿŹŵƮŤƿŹƺĮƫřƶƨǀƯŚĮƴƷ ƁƹŹƲƿřŻřƵŵŚƠŤſřŶſŹƾưƳƶŬǀŤƳƶŝźŤƸŝśŚƷśřƺūƲŤƟŚƿƽřźŝ ƶŝ ŶƳřƺŤŝ ƮŤƿŹƺĮƫř ƹ ƵŵźƧ źǀǀƜţ ƺŬŤƀū ŶƳƹŹ ƶƧ ŵƺƃƾƯ ŜŞſ Ʊō ƶŝ LjŞƣ ƶƧ ŶƴƧ řŶǀě ƾſźŤſŵ śřƺū ƽŚƌƟ Żř ƾƿŚƷŢưƀƣ
ƽŚƷśřƺūƶŝŶƳřƺţƾƯƮŤƿŹƺĮƫřƶŬǀŤƳŹŵŵƺŝƵŵźƨƳřŶǀěƾſźŤſŵ ŶƷŵƂƿřżƟřřŹŚƷśřƺūŢǀƠǀƧƹŶŝŚƿŢſŵƽźţšƹŚƠŤƯ
ƲƿźţŵźŝŹŚĩźě ƹ ƲƿźŤưƸƯ Żř ƾĪƿ ƱřƺƴƗ ƶŝ ĨǀŤƳĥ ƮŤƿŹƺĮƫř
Ʋƿř Śŝ ƹ Ţſř ƝƹźƘƯ ƽŹŚĪŤŝřřźƟ ƽŚƷƮŤƿŹƺĮƫř Ʋǀŝ Źŵ ŚƷƮŤƿŹƺĮƫř ƪŗŚƀƯ ƾƳŶƃ ƽŚƌƟ Źŵ źŤƸŝ ƾŤĩźů ƱřƺţƾƯ ƾƟŵŚƈţ ƁƹŹ
ŵŹƹōŢſŶŝƽźŤƸŝƽŚƷśřƺūƶŬǀŤƳŹŵƹŵřŵŹřźƣƾſŹźŝ ƶƫŚƀƯƽřźŝƾƳŶƃśřƺūźƷƱŵřŵƱŚƄƳƁƹŹřŶŤŝřŹŵƂŴŝƲƿřŹŵ ƶĩŶƿŶūŜǀĩźţƾƗƺƳžĜſƹƵŵřŵƱŚƄƳřŹƶǀƬƤƳƶƬǀſƹƾŝŚƿźǀƀƯ ƮŤƿŹƺĮƫř Ʋƿř ƶŝ ŢŞƀƳ ŚƯř Ƶŵƺŝ ƽřƶƐƤƳ Ĩţ ƖƏŚƤţ ƁƹŹ Ɩǀſƺţ ƁƹŹřŶŤŝřŹƺƔƴƯƲƿřƽřźŝŵƺƃƾƯŵŚƸƴƄǀěƶƫŚƀƯƽřźŝŢſřźţřŹŚĩ źƔƳŵŹƺƯŜǀĩźţƁƹŹžĜſƹƵŵźĩƞǀƇƺţřŹƽřƶƐƤƳĨƿƖƏŚƤţ Ĩƿ Żř ƾƳŶƃ śřƺū Ĩƿ ƱŵřŵƱŚƄƳ ƽřźŝ ŵƺƃƾƯ Ƶŵřŵ ŭźƃ ƵŵŚƠŤſřŢſřƵŶƃƵŵřŵƱŚƄƳêƪĪƃŹŵƶĩƾƄŴŝƹŵƭƹŻƺƯƹźĩ ƶƬǀſƺŝŶƿŚŝƶĩŢſřƾƿŚƷƽźŤƄƯƵŶƴƷŵƱŚƄƳƩƹřŢưƀƣŵƺƃƾƯ ƶĩ ƾţŹƺƇŹŵŶƳźǀĭŹřźƣšŚƣLjƯŵŹƺƯŜǀţźţ ƶŝƶǀƬƤƳƶƬǀſƹźƷ

ƵŵřŵƱŚƄƳ n14 ƹ m3 ŚŝƶƫŚƀƯĨƿÒƪĪƃŹŵƩŚŨƯŹƺƐŝ ÐÎƽźŤƄƯŪƴěƶĩŵŹřŵƵŹŚƃřƶŤĪƳƲƿřƶŝƪĪƃƲƿřŢſřƵŶƃ ƶĩ ƮŤƿŹƺĮƫř ŹřźĪţ źƷ ƽŚƸŤƳř Źŵ ƲƿřźŝŚƴŝ ŵƺƄƳ ŢƟŚƿ ƮŤƿŹƺĮƫř
ƱōƽƹŹřŹƶƳŚĭƶſƵŶƴƷŵŵƺŞƸŝƮŤƿŹƺĮƫřŶƯōŢſŶŝŹřŶƤƯƲƿźŤƸŝ ƶŤĪƳ Ʋƿř ƶŝ ƶūƺţ ƮǀƴĩƾƯ śŚŴŤƳř řŹ śřƺū ƲƿźŤƸŝ ƹ Ƶŵźĩ řźūř
Śŝ Śţ ŵƺƃƾƯ Ƶźǀųŷ śřƺū ƲƿźŤƸŝ ƶƳŚĭ ƶſ ƾƬŰƯ ƽƺŬŤƀū ŶƿōŢſŶŝƮŤƿŹƺĮƫřśřƺūƲƿźŤƸŝŚƷśřƺūƲƿřƶƀƿŚƤƯ
Ŷƴĩ ơŶƇ Ŷƃ ƵŹŚƃř Ʊō ƶŝ LJŚŝ Źŵ ƶĩ ƶƫŚƀƯ ƽŚƷŢƿŵƹŶŰƯ Źřźƣ ƮŤƿŹƺĮƫř ƁźƿŸě ŵŹƺƯ ƾŤƫŚů Źŵ ƎƤƟ ŚŤĪƿ Źƺţ Ʋƿř ƲǀƴĤưƷ śřƺūƶŝŢŞƀƳƶƫŚƀƯƽřźŝřŹƽźŤƸŝŹřŶƤƯŶƿŶūŹƺţƶƧŵźǀĭƾƯ ƝŸůƪưƗƶĩŢſřƽŹƹźƋƶŤĪƳƲƿřƶŝƶūƺţŵŹƹōŢſŶŝƾƬŞƣ ƶƯřŵř ƾƿŚū Śţ ƾƫřƺŤƯ ŹƺƐŝ řŹ ŚƸƳō ƵŹŚŝƹŵ ƱŵźƧƪƈŤƯ ƹ ƱŚưĩ ƶſ ƽřźŝ ƽŶƿŶū ƵŶƴƷŵŵƺŞƸŝ ŢƧźů ĢǀƷ źĮƿŵ ƶĩ ŶƴĩƾƯ řŶǀě





















قیمت: تومان

پاسخ دهید