the selective full truckload multi-depot vehicle routing problem with time windows: formulation and a genetic algorithm

The process of an empty backhaul truck returning to its home domicile after a regular delivery journey has attracted many logistics companies in the modern world economy. this paper studies a selective full truckload multi-depot vehicle routing problem with time windows (sftmdvrptw) in an empty return scenario. this problem aims at planning a set of backhaul routes for a fleet of trucks that serve a subset of selected transportation demands from a number of full truckload orders to maximize the overall profit, given constraints of availability and time windows. after reviewing the literature related to full truckload vehicle routing problems, based on the professional characteristics encountered as well as on the resolution approaches used, we formulate a mixed-integer linear programming (milp) model for the sftmdvrptw. since the problem is np-hard, we propose a genetic algorithm (ga) to yield a near-optimal solution. a new two-part chromosome is used to represent the solution to our problem. through a selection grounded on the elitist and roulette method, a new crossover operator called “selected two-part crossover chromosome (s-tcx)” and an exchange mutation operator, new individuals are generated. the proposed milp model and ga are evaluated on newly randomly generated instances. the findings prove that the ga significantly outperforms the cplex solver in solution quality and cpu time.