Metaheuristic Algorithms for the Vehicle Routing Problem with Time Window and Skill Set Constraints

Abstract

A subcontractor assigns installation services requested by a group of geographically scattered customers to its technicians daily. Requested services by the customers require a set of skills and should start during customers’ availability periods. Each technician has certain skills, and limited availability daily to perform the services. Subcontractor’s revenue from the installation jobs is fixed based on standard time for each type of job. The problem of assigning the optimum subset of the jobs to eligible technicians and identifying the optimum route to perform the services is classified as NP-Hard and is a challenging problem to solve. In this research, a vehicle routing problem with time window and skill set constraints (VRPTWSS) is considered to address the problem. Due to the NP-hardness of vehicle routing problem, two metaheuristic algorithms are proposed to solve this problem. Performance of these approaches is evaluated against an MILP model for smaller problems via simulation.