Synchronizing delivery and installation with vehicle sharing: A hybrid adaptive large neighborhood search

This paper presents the real-life synchronized delivery and installation with vehicle sharing problem (SDIVSP). Two fleets of vehicles serve a set of customers within their specified time windows. Delivery vehicles drop products to customers while installation vehicles drop and pick up technicians without necessarily waiting for them. Delivery must precede installation. This paper models SDIVSP as a mixed integer linear program, which solves small-sized instances. For large instances, this paper proposes a heuristic HALNS that hybridizes adaptive large neighborhood search and variable neighborhood search. Extensive experimentation provides computational evidence of the superiority of HALNS when solving well-known benchmark instances of (synchronized) vehicle routing problems with time windows and its effectiveness in tackling newly proposed SDIVSP instances. HALNS outperforms two state-of-the-art algorithms by an average 6.41% and 12.43% on synchronized vehicle routing with time windows benchmark sets. It further provides computational evidence of the benefits of shared installation vehicles: Total cost decreases by 41.72% and 35.35% as the installation vehicle capacity increases for tight and large time windows respectively.