Artificial Immune System-based algorithm for vehicle routing problem with time window constraint for the delivery of agri-fresh produce

摘要

This paper addresses the problem of delivering continuously deteriorating agri-fresh produce from a wholesaler to a number of retailers, within specific time windows. The prime objective is to decide the routes in such a way that the overall cost incurred in transportation, deterioration and penalty is minimised. To model these conflicting objectives a mathematical modelling approach is proposed. The Vehicle Routing Problem with Time Windows (VRPTW) is a Non-deterministic Polynomial-time hard (NP-hard) problem, without considering the business constraints, and becomes computationally prohibitive with the increase in number of retailers. To solve the VRPTW within feasible time limits, Artificial Immune System (AlS)-based solution methodology is proposed. The algorithm is tested on real-life instances generated from Azadpur wholesale market, New Delhi (India). An experiment is performed on the same problems with other algorithms, such as Genetic Algorithm (GA) and Simulated Annealing (SA), to compare the effectiveness and efficiency of the proposed approach. It is found from the quality of solution and rate of convergence that AIS performed better compared to the other applied approaches.