Modified Ant Colony Algorithm for the Vehicle Routing Problem with Time Windows

M Taghavifard, K. Sheikh & A. Shahsavari,

M Taghavifard, Assistant Prof., Allame Tabatabaei Univ., Tehran-Iran,
K. Sheikh, Industrial Engineering Dept., Faculty of Graduate Studies, Azad Univ., Tehran South Branch,
A. Shahsavari, Industrial Engineering Dept., Faculty of Graduate Studies, Azad Univ., Tehran South Branch,



1268732040128Downloaded from at 16:54 IRST on Saturday November 4th 2017

Downloaded from at 16:54 IRST on Saturday November 4th 2017

Vehicle Routing
Problem with
Time Windows,
Ant Colony
Algorithm, Solomon testproblems Vehicle Routing Problem with Time Windows (VRPTW) is an NP-Complete Optimization Problem. Even finding an optimal solution for small size problems is too hard and time-consuming. The objective of VRPTW is to use a fleet of vehicles with specific capacity to serve a number of customers with dissimilar demands and time window constraints at minimum cost, without violating the capacity and time window constraints. This problem has been solved with a number of heuristic and meta-heuristic solution algorithms and optimal or near optimal solutions gained. In this paper, a modified Ant Colony algorithm is proposed. In this algorithm we tried to simplify the solution procedure and computational complexities of ant colony metaheuristic. To gain this capability, we sacrificed some computational accuracy. Testing the solution procedure on the Solomon test-problems showed that this algorithm is capable of generating relatively good solutions.
æèííçåŶƬūçƵŹŚưƃ ŶǀƫƺţŢƿźƿŶƯƹƖƿŚƴƇƾſŶƴƸƯƾƬƬưƫřƲǀŝƶƿźƄƳ’




NP-Complete ƪŗŚƀƯ ƵźƯŻ Źŵ ƾƳŚƯŻ ƽŚƷ ƵźŬƴě ƵřźưƷ ƶŝ ƶǀƬƤƳ ƪƿŚſƹ ƾŝŚƿźǀƀƯ ƶƬŘƀƯ
Żř ƽŹŚǀƀŝ Ǝſƺţ ƱƺƴĩŚţ ƶƬŘƀƯ Ʋƿř ŶƳŵźĮƳ ƊƤƳ ƾƳŚƯŻ ƵźŬƴě żǀƳ ƹ ŚƷŢǀƟźƓ ƹ ƵŶƃ ƶƴǀưĩ ƾŝŚƿźǀƀƯƶƬŘƀƯ
ƾƳƺƬĩƮŤƿŹƺĮƫř ƶƳƺưƳƱŚĮģŹƺƯ
ƶƴǀƸŝśřƺūƶŝĨƿŵżƳŚƿƶƴǀƸŝƽŚƸŝřƺūƹƵŶƃƖƣřƹƪůŵŹƺƯƽŹŚĪŤŝřřźƟƹƽŹŚĪŤŝřƪůƽŚƸƃƹŹ SolomonƪŗŚƀƯ

íëíççƩƺƇƹŲƿŹŚţ íìæåæêŜƿƺƈţŲƿŹŚţƾƿŚŞƏŚŞƏƶƯLjƗƵŚĮƄƳřŵŹŚƿŵŚŤſřŵźƟƽƺƤţƾƤţŶưŰƯźŤĩŵ
keyvansheikh@gmail.comśƺƴūƱřźƸţŶůřƹƾƯLjſřŵřŻōƵŚĮƄƳřŵƾƬǀưĪţšLjǀƈŰţƵŶĪƄƳřŵƖƿŚƴƇƾſŶƴƸƯŶƃŹřŽŚƴƃŹŚĩŲǀƃƱřƺǀĩ Sharian61@gmail.comśƺƴūƱřźƸţŶůřƹƾƯLjſřŵřŻōƵŚĮƄƳřŵƾƬǀưĪţšLjǀƈŰţƵŶĪƄƳřŵƖƿŚƴƇƾſŶƴƸƯŶƃŹřŽŚƴƃŹŚĩƽŹřƺƀƸƃƲƿŹō

ƱōŹŵƹƵŶƿŵźĭŵŚƸƴƄǀěƱŚĮģŹƺƯƾƳƺƬĩƮŤƿŹƺĮƫřƵŶƃŭLjƇřƕƺƳƶƫŚƤƯƲƿřŹŵŢſřƵŶƃƪƇŚů ƶŤŞƫřžŵŵźĭƮƷřźƟƪůƁƹŹŢƫƺƸſƹśŚƴŤūřƾţŚŞſŚŰƯƽŚƷƾĭŶǀĤǀěŻřƲĪưƯŶůŚţƵŶƃƾƘſ ŚŝŢſřƵŶƃƾţŚŞſŚŰƯŢƣŵŻřƾưĩŹřŶƤƯƱŵřŵŢſŵŻřƶŝźŬƴƯƾŤǀƬŝŚƣƲǀƴģƲŤƟźĭźƔƳŹŵ
ƲƿřƶĩŵƺưƳŹŚĪƃōSolomonƪŗŚƀƯƶƳƺưƳŻřƽŵřŶƘţƽƹŹźŝƽŵŚƸƴƄǀěƮŤƿŹƺĮƫřƽřźūřƩŚůƲƿř ŶƃŚŝƾƯřŹřŵřŹśƺųľŚŤŞƀƳƽŚƷśřƺūŶǀƫƺţƾƿŚƳřƺţƮŤƿŹƺĮƫř

šƹŚƠŤƯƾƳŚƯŻƽŚƷŢƿŵƹŶŰƯƹŚƷŚƋŚƤţŚŝƱŚƿźŤƄƯŻřƾƴǀƘƯŵřŶƘţ ŶƷŵƾƯƍŚŞţŹřƱŚƿźŤƄƯƲƿřƾƯŚưţƶŝřŹƽżĩźƯƺěŵƶĩƽřƶĪŞƃƹ źƠƇƵŹŚưƃƽźŤƄƯƱřƺƴƗƶŝřŹƽżĩźƯƺěŵƾĭŵŚſƽřźŝŶƃŚŝƾƯ N1 Śŝ źŝřźŝ ƱŚƿźŤƄƯ ƪĩ ŵřŶƘţ śŚƀů Ʋƿř Śŝ ƹ ƶŤƟźĭ źƔƳŹŵ ƺěŵŻřŢſřšŹƺƇƲƿŶŝƶǀƬƤƳƶƬǀſƹźƷƾŝŚƿźǀƀƯŵźĪƿƹŹŶƃŚŝƾƯ
ŵŵźĭƾƯŻŚŝƽżĩźƯƺěŵ ƹŹŚŞĪƿŶƳřƺţƾƯŚƸƴţƹŶƃŚŝƾƯ miƽŚƋŚƤţƽřŹřŵ i ƽźŤƄƯźƷ ƽřŹřŵ k ƶǀƬƤƳ ƶƬǀſƹ ŵƺƃ šŚƣLjƯ ƶǀƬƤƳ ƶƬǀſƹ Ĩƿ ŚƸƴţ Ǝſƺţ ƕƺưŬƯŚŝƽƹŚƀƯŚƿƹźŤĭŹżŝŶƿŚŝ qk ƹŶƃŚŝƾƯ qk ŢǀƟźƓ šŚƣLjƯ řŹ ŚƸƳō ƶƬǀſƹ Ʋƿř ƶĩ ŶƃŚŝ ƾƳŚƿźŤƄƯ ƾƯŚưţ ƽŚƋŚƤţ ƪĩ
ƶĩ Ţſř ƵŶƃ ƞƿźƘţ Ƃǀě Żř ƾƳŚƯŻ ƵŻŚŝ Ĩƿ ƽřŹřŵ ƽźŤƄƯ źƷ
ƽřźŝ liŵƹŹƹƱŚƯŻƲƿźţźƿŵƹ ei ŵƹŹƹƱŚƯŻƲƿźţŵƹŻƪƯŚƃ
ƶǀƬƤƳ ƪƿŚſƹ ŶƃŚŝƾƯ ƽźŤƄƯ Ʊō šŚƣLjƯ ŢƸū ƶǀƬƤƳ ƪƿŚſƹ ŶƴſźŝƽźŤƄƯƪŰƯƶŝ liŵƹŹƹƱŚƯŻƲƿźţźƿŵŻřƪŞƣŢƀƿŚŝƾƯ Ŷƴſźŝ ƽźŤƄƯ ƪŰƯ ƶŝ ei ŵƹŹƹ ƱŚƯŻ ƲƿźţŵƹŻ Żř ƪŞƣ źĭř ƹ ŶƿōƾƯŵƺūƺŝ wiŹŚƔŤƳřƱŚƯŻŚŬƴƿřŹŵƹŶƴƳŚưŝźƐŤƴƯŶƿŚŝƵŚĮƳō ƱŚƯŻƵŶƳźǀĭźŝŹŵƶĩŶƃŚŝƾƯ f i žƿƹźſƱŚƯŻƽřŹřŵƽźŤƄƯźƷ ŢſŚƴƘƯƲƿŶŝƺěŵƾƳŚƯŻƵźŬƴěŶƃŚŝƾƯŚƷLJŚĩƽźǀĭŹŚŝŹŚŝƶǀƬŴţ
ƱŚƯŻŻřƪŞƣŶƿŚŝŵƺƃƾƯũŹŚųƺěŵŻř e0ƱŚƯŻƶĩƶƬǀſƹźƷƶĩ
ŵŵźĭŻŚŝƱōƶŝ l0
ƎŴƫř ƮǀƤŤƀƯ ƶƬƇŚƟ ŽŚſřźŝ ƱŚƿźŤƄƯ ƾƯŚưţ Ʋǀŝ ŢƟŚƀƯ ĨƿŚŝźŝřźŝƶƬǀſƹźƷŢĩźůŢƗźſƹŵƺƃƾƯƶŞſŚŰƯƾſƹŶǀƬƣř
ŢƫƺƸſ ŦƗŚŝ ƉźƟ Ʋƿř ŶƃŚŝƾƯ ƱŚƯŻ Ŷůřƹ źƷ Źŵ ŢƟŚƀƯ Ŷůřƹ
Minimize NNK ci, j X ijk
1268732040128Downloaded from at 16:54 IRST on Saturday November 4th 2017

Downloaded from at 16:54 IRST on Saturday November 4th 2017

i0 j0 k1
Subject to: N
 X0 jk 1,
j1 for k 1,2,…,K æ
N  X i0k 1, for k 1,2,…,K ç

ƕƺƳ Ĩƿ ƾƳŚƯŻ ƽŚƷƵźŬƴě ƵřźưƷ ƶŝ ƶǀƬƤƳ ƪƿŚſƹ ƾŝŚƿźǀƀƯ ƶƬŘƀƯ
ƪƿƺŰţƶƬưūŻřƾƳƺĭŚƳƺĭƽŚƷŵźŝŹŚĩƹŢſřƽźǀĭ ƮǀưƈţƶƬŘƀƯ ƲƿřŵŹřŵƹƖƿŻƺţżĩřźƯƶſŹŶƯŽƺŝƺţřƾŝŚƿźǀƀƯƶƯŚƳŻƹŹƹƶƯŚƳ
ƹ ŚƷŚƋŚƤţ Śŝ ƱŚƿźŤƄƯ Żř ƽřƶƗƺưŬƯ ƹ ƽżĩźƯ ƩŚƴǀƯźţ ƺěŵ
ƺěŵ Żř ƶǀƬƤƳ ƪƿŚſƹ Żř Ĩƿ źƷ ŶƃŚŝƾƯ šƹŚƠŤƯ ƾƳŚƯŻ ƽŚƷƵźŬƴě
ŻřƾƐŴţƱƹŶŝřŹŚƷLJŚĩƹ ŻŚƛōřŹŵƺųŢĩźůƽżĩźƯ
ƺěŵ ƶŝ ľřŵŶŬƯ ŢƿŚƸƳ Źŵ ƹ ŶƴƿŚưƳƾƯ ƪưů ƾƳŚƯŻ ƽŚƷŢƿŵƹŶŰƯ
ƹ ŹŚŞĪƿ ŚƸƴţ ŶƴƳřƺţƾƯ ƱŚƿźŤƄƯ Żř

قیمت: تومان

پاسخ دهید