Vehicle Routing Problem with Synchronization for Mobile Health Clinics

As an important means of providing medical services in developing countries and remote areas, Mobile Health Clinics (MHCs) focus on distributing medical supplies and providing basic health needs to underserved communities. We model this problem as a vehicle routing problem with multiple synchronization constraints and heterogeneous demand (VRPMSC-HD) and formulate a mixed integer linear programming (MILP). We propose a matheuristic based on adaptive large neighborhood search (ALNS) combined with an intensive local search phase to solve large-scale instances on the model. We assess the advantages and disadvantages of the proposed approach by comparing its solutions with the solutions of the vehicle routing problem with multiple trips (VRP-MT). Interestingly, the proposed approach leads to longer total traveled distance/time when taking into account the routing of the resupply truck and the MHCs. On the other hand, the proposed approach achieves significant reduction in the latest arrival metric leading to faster completion of services and higher utilization of a fleet of MHCs.