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, dr.taghavifard@gmail.com
K. Sheikh, Industrial Engineering Dept., Faculty of Graduate Studies, Azad Univ., Tehran South Branch,keyvansheikh@gmail.com
A. Shahsavari, Industrial Engineering Dept., Faculty of Graduate Studies, Azad Univ., Tehran South Branch, Sharian61@gmail.com

Keywords ABSTRACT

Keywords ABSTRACT

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

Downloaded from ijiepm.iust.ac.ir 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.
æèííçåŶƬūçƵŹŚưƃ ŶǀƫƺţŢƿźƿŶƯƹƖƿŚƴƇƾſŶƴƸƯƾƬƬưƫřƲǀŝƶƿźƄƳ’

ƾŝŚƿźǀƀƯƶƬŘƀƯƪůŢƸūƱŚĮģŹƺƯƾƳƺƬĩƵŶƃŭLjƇřƁƹŹƶŗřŹř
ƾƳŚƯŻƽŚƷƵźŬƴěƵřźưƷƶŝƶǀƬƤƳƪƿŚſƹ
ƽŹřƺƀƸƃƲƿŹōƹŲǀƃƱřƺǀĩŵźƟƽƺƤţƾƤţŶưŰƯ
įŶǀƬĩšŚưƬĩ
ƵŶǀĪģ

įŶǀƬĩšŚưƬĩ

ƵŶǀĪģ


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

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

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

šƹŚƠŤƯƾƳŚƯŻƽŚƷŢƿŵƹŶŰƯƹŚƷŚƋŚƤţŚŝƱŚƿźŤƄƯŻřƾƴǀƘƯŵřŶƘţ ŶƷŵƾƯƍŚŞţŹřƱŚƿźŤƄƯƲƿřƾƯŚưţƶŝřŹƽżĩźƯƺěŵƶĩƽřƶĪŞƃƹ źƠƇƵŹŚưƃƽźŤƄƯƱřƺƴƗƶŝřŹƽżĩźƯƺěŵƾĭŵŚſƽřźŝŶƃŚŝƾƯ N1 Śŝ źŝřźŝ ƱŚƿźŤƄƯ ƪĩ ŵřŶƘţ śŚƀů Ʋƿř Śŝ ƹ ƶŤƟźĭ źƔƳŹŵ ƺěŵŻřŢſřšŹƺƇƲƿŶŝƶǀƬƤƳƶƬǀſƹźƷƾŝŚƿźǀƀƯŵźĪƿƹŹŶƃŚŝƾƯ
ƶŝŢƿŚƸƳŹŵƹŶƴĩƾƯšŚƣLjƯřŹƱŚƿźŤƄƯŶƿŚưƳƾƯŻŚƛōřŹŢĩźů
ŵŵźĭƾƯŻŚŝƽżĩźƯƺěŵ ƹŹŚŞĪƿŶƳřƺţƾƯŚƸƴţƹŶƃŚŝƾƯ 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
ƎŴƫř ƮǀƤŤƀƯ ƶƬƇŚƟ ŽŚſřźŝ ƱŚƿźŤƄƯ ƾƯŚưţ Ʋǀŝ ŢƟŚƀƯ ĨƿŚŝźŝřźŝƶƬǀſƹźƷŢĩźůŢƗźſƹŵƺƃƾƯƶŞſŚŰƯƾſƹŶǀƬƣř
ŢƫƺƸſ ŦƗŚŝ ƉźƟ Ʋƿř ŶƃŚŝƾƯ ƱŚƯŻ Ŷůřƹ źƷ Źŵ ŢƟŚƀƯ Ŷůřƹ
ƶŝƶǀƬƤƳƪŗŚſƹƾŝŚƿźǀƀƯƶƬŘƀƯƾƋŚƿŹƩŶƯŵƺƃƾƯƶƬŘƀƯƪů
>çé@ŢſřƵŶƃƶŗřŹřľLjƿŷƾƳŚƯŻƽŚƷƵźŬƴěƵřźưƷ
Minimize NNK ci, j X ijk
1268732040128Downloaded from ijiepm.iust.ac.ir at 16:54 IRST on Saturday November 4th 2017

Downloaded from ijiepm.iust.ac.ir 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 ç
i1

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



قیمت: تومان


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