OPTIMIZING THE PROCESS OF PICK-UP AND DELIVERY WITH TIME WINDOWS USING ANT COLONY AND TABU SEARCH ALGORITHMS

Amalia, Imas Saumi; Bakhtiar, Toni; Jaharuddin, Jaharuddin · 2022 · DOAJ

DOI: 10.30598/barekengvol16iss2pp651-662

archive: archived pipeline: cataloged verified

Get this paper ↗ (DOI — opens at the source; we link to it, we don't host it)

Summary

This paper addresses the Traveling Salesman Problem with Pick-up and Delivery, Handling Costs, and Time Windows (TSPPDHTW), a combinatorial optimization problem relevant to goods shuttle services. The research is motivated by the inefficiency of exact methods, which require exponentially long computation times for large datasets, making them impractical for real-life applications. The problem involves optimizing routes for a single vehicle with limited capacity and single transport access, handling two types of goods (deliveries and pickups), and adhering to customer time windows. The objective is to minimize the total time, comprising both travel time and handling time, where handling time accounts for the rearrangement of goods blocked by other items during unloading. To solve this NP-hard problem efficiently, the authors developed a hybrid metaheuristic algorithm called ACOTS, combining Ant Colony Optimization (ACO) and Tabu Search (TS). The study utilized a case study involving 14 bicycle shops in Bogor, Indonesia, with travel data obtained from Google Maps and hypothetical demand and time window data. The ACOTS algorithm was implemented using OCTAVE software. Significant modifications were made to standard ACO and TS procedures to handle TSPPDHTW constraints. These included adding clustering functions to group customers by overlapping time windows, constraint evaluation mechanisms for vehicle capacity and time windows, a "cutting tour" function to resolve stuck nodes, and a specific goods arrangement policy to minimize handling time. Additionally, the TS component was modified to evaluate moves based on feasibility regarding capacity and time windows. The study first conducted parameter simulations to determine optimal settings for ACO parameters ($\alpha$, $\beta$, $\rho$, and number of ants $m$). Results indicated that $\beta$ significantly influenced the trade-off between travel and handling costs, with higher values reducing travel costs but increasing handling costs. The optimal configuration was identified as $\alpha=5$, $\beta=1$, $\rho=0.5$, and $m=5$. When applied to the case study, the ACOTS algorithm achieved a solution with a total cost of 412.30 minutes. This result represented a deviation of approximately 22% from the optimal solution found by the exact method. However, the computational efficiency was drastically improved; ACOTS required only 61 seconds of computation time, compared to approximately 134 hours required by the exact method. The paper concludes that ACOTS provides a near-optimal solution with significantly reduced computational time, making it a viable strategy for real-world logistics optimization involving complex constraints like handling costs and time windows.

Provenance

The full processing record for this entry. Every stage of this paper's journey through the pipeline is logged — what ran, with which tool and model, how many attempts it took, and when it last completed.

Summary generated by qwen3.6-27b-prismaquant on 2026-06-26; verification: verified.

Topics

Ranked by relevance to this paper. Hover a topic for its definition.

• last mile delivery