Study of ALNS-TS algorithm on VRPSDPTW and its implementation

• Main Authors: Kurniawati, Wanda, Wahyuningsih, Sapti, Yasin, Mohamad
• Format: Conference Proceeding
• Language: English
• Subjects: Algorithms; Customers; Software; Tabu search; Vehicle routing; Windows (intervals)
• ISSN: 0094-243X; 1551-7616
• DOI: 10.1063/5.0234530

Problems with the route of distribution of goods from depots to customers with delivery and return constraints being carried out simultaneously within a certain time limit can be solved using the Vehicle Routing Problem with Simultaneous Delivery and Pickup and Time Window (VRPSDPTW). In this article, the VRPSDPTW problem is solved using the Adaptive Large Neighborhood Search – Tabu Search (ALNS-TS) algorithm. Algorithm implementation with Borland Delphi software with waterfall method (requirement, design, implementation, verification). There are three stages in the ALNS-TS algorithm, namely initial solution initialization with ALNS, solution improvement with Tabu Search, and acceptance of optimal conditions. Program inputs are points that represent depots and customers, distances between customers, requests and returns, opening and closing times, vehicle capacity and speed, parameters p, unloading time, starting time, TS iterations, and ALNS-TS iterations. The program has been tested on several customer data, namely 6, 25, 50 and 75 customers. The output of the program is in the form of the route formed, the total distance traveled, the number of vehicles used, and graph visualization. Improvements in tabu search (TS) have improved the solutions obtained from the original ALNS algorithm. Testing the simulation data with the program shows that the solution obtained by the ALNS-TS algorithm has a smaller distance compared to the ALNS algorithm. An example of a real problem that is solved by implementing the ALNS-TS algorithm using software is given.