Optimization and Re-optimization with Heuristics the Capacitated Vehicle Routing Problem with Time Windows under Uncertain Demands

Pavita

Abstract

Nowadays, business organizations are moving towards seamless and sophisticated technology to aid with their day-to-day supply chain operations. Tactical and operational levels of transport consist of making medium and short-term decisions, including planning of delivery schedules, routes, and load plans. Manual planning of delivery routes are not always giving optimal routes and scheduling. As such, at times higher charges might incur or customer’s satisfactions are compromised.

Particle Swarm Optimization (PSO) of metaheuristics method is a good approach to balance the trade-off between obtaining optimal solutions and obtaining results in reasonable amount of time in solving Capacitated Vehicle Routing Problem with Time Windows (CVRPTW). As information regarding customers’ demands are gradually revealed over horizon time, routing decision is necessary by considering the assignment of customers to vehicles. The procedure to solve this problem called route reoptimization, which is the best option for minimizing expected transportation cost without incurring failures of unsatisfied demand on a route. PSO was able to solve reoptimization of CVRPTW with uncertain demand (CVRPTWUD).

From the research, implementing PSO will have an average of 11.640% optimality gap when solving the identical CVRPTW model as compared to exact method.

By including or reducing new customers in the system, a reoptimization was performed with objective to minimize dispersion and total route length. A classic PSO optimization was performed on all instances using the original and new customers’ information as comparison to minimize total cost.

The results from the study were promising and show that classic PSO approach was indeed quite effective in solving the considered problems, be it static CVRPTW model or dynamic CVRPTWUD using reoptimization procedures. Comparing costs incurred in manual planning and costs incurred by implementing PSO, PSO will have a total saving of $4,236.104 annually in terms of lower routes costing and time saved.

In order to achieve better approximation results within shorter computing times, it is recommended to further the study in terms of different combination of tuning parameters or applications of modifications of PSO method in solving the problems.