Two-stage vehicle routing problem with arc time windows: A mixed integer programming formulation and a heuristic approach

Creative Commons License

Cetinkaya C., Karaoğlan İ., Gökçen H.

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, cilt.230, ss.539-550, 2013 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 230
  • Basım Tarihi: 2013
  • Doi Numarası: 10.1016/j.ejor.2013.05.001
  • Dergi Adı: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.539-550
  • Anahtar Kelimeler: Logistics, Vehicle routing problem with arc time windows, Memetic algorithm, Mathematical formulation, SUBTOUR ELIMINATION CONSTRAINTS, EFFECTIVE MEMETIC ALGORITHM, SCHEDULING PROBLEMS, CUT ALGORITHM, BRANCH, SEARCH
  • Gazi Üniversitesi Adresli: Evet

Özet

In this paper, we introduce a new variant of the Vehicle Routing Problem (VRP), namely the Two-Stage Vehicle Routing Problem with Arc Time Windows (TS_VRP_ATWs) which generally emerges from both military and civilian transportation. The TS_VRP_ATW is defined as finding the vehicle routes in such a way that each arc of the routes is available only during a predefined time interval with the objective of overall cost minimization. We propose a Mixed Integer Programming (MIP) formulation and a heuristic approach based on Memetic Algorithm (MA) to solve the TS_VRP_ATW. The qualities of both solution approaches are measured by using the test problems in the literature. Experimental results show that the proposed MIP formulation provides the optimal solutions for the test problems with 25 and 50 nodes, and some test problems with 100 nodes. Results also show that the proposed MA is promising quality solutions in a short computation time. (C) 2013 Elsevier B.V. All rights reserved.