Logistics companies are under increasing pressure to overcome operational challenges and sustain profitable growth while dealing with the newest requirements of their customers. One of the remedies designed to cope with a higher number of shipments is to use multi-compartment city vans to ensure all forms of integration with deliveries. In the area of city logistics, the most common type of delivery involves storing inventory in a central warehouse and to deliver customers’ orders with multi-compartment vehicles. The problem under study is denoted as the vehicle routing problem with multi-compartment vehicles which are to operate from a single depot to visit customers within the chosen time period by minimizing major operational costs. We propose an enhanced adaptive large neighborhood search algorithm for the investigated routing problem. The computational results highlight the efficiency of the proposed algorithm in terms of both solution quality and solution time and also provide useful insights for city logistics.