SMT-LH: A New Satisfiability Modulo Theory-Based Technique for Solving Vehicle Routing Problem with Time Window Constraints. (11th January 2019)

• Record Type: Journal Article
• Authors: Rizkallah, Lydia W; Ahmed, Mona F; Darwish, Nevin M
• Editors: Alechina, Natasha
• Is Part Of: Computer journal. Volume 63:Number 1(2020)
• Page Start: 91
• Page End: 104
• Publication Date: 2019-01-11
• Subjects: vehicle routing problem -- satisfiability modulo theories -- first-order-logic -- difference logic -- local search improvement heuristics; Computers -- Periodicals; 005.1
• DOI: 10.1093/comjnl/bxy127
• Languages: English
• ISSNs: 0010-4620

Abstract

Abstract: The vehicle routing problem (VRP) is the problem of designing a specific number of routes to serve a given number of customers while achieving minimum total travel distance and minimum number of vehicles. VRP with time window constraints (VRPTW) restricts that the service time of each customer should start within a time window. This problem and its variations are known to be NP-hard. This paper proposes a transformation of the NP-hard problem into another. The approach is based on satisfiability modulo theories (SMT) in order to take advantage of its relative CPU time competitiveness. This poses transformability challenges in order to apply SMT solving techniques on the VRPTW. In this work, SMT is successfully applied to solve the VRPTW. The solution quality proves to be competitive to other optimization techniques since the solving time is significantly decreased opening the door to solve much larger problems. In addition, it sets a proof for using SMT efficiently as a main step for solving optimization problems.