This article addresses a Periodic Vehicle Routing Problem with Time Window and Service Choice problem. This problem is basically a combination of existing Periodic Vehicle Routing Problem with Time Window and Periodic Vehicle Routing Problem with Service Choice. We model it as a multi objective problem. To solve this problem, we develop a heuristic algorithm based on Improved Ant Colony Optimization (IACO) and Simulate Annealing (SA) called Multi Objective Simulate Annealing – Ant Colony Optimization (MOSA-ACO). Improvements are made in following respects: a) a Euclidean distance based solution acceptance criterion is developed; b) a parameter control pattern is designed to generate different initial solutions; c) several local search strategies are added. Benchmark instances generated from Solomon’s benchmark instances and Cordeau’s benchmarks instances are applied. Comparison algorithms include four population based heuristics and IACO. Computation experiment results show that MOSA-ACO algorithm has a good performance on solving this problem.

Introduction

In this article, we propose a special variant of existing Periodic Vehicle Routing Problem (PVRP) called Periodic Vehicle Routing Problem with Time Window and Service Choice (PVRPTW-SC). We give out a problem model which is an extension of PVRP-SC problem model. Then, a hybrid heuristic algorithm called Multi-Objective Simulation Annealing – Ant Colony Optimization (MOSA-ACO) is applied to this problem. Finally, computation experiment results are reported. Experiment instances include instances generated from VPRTW benchmark instances and PVRPTW benchmark instances. Experiment results show that the MOSA-ACO has a good performance on PVRPTW-SC. This research is first inspired by Jiting et al. [1]. In this paper, a geostationary orbit (GEO) satellite observation planning problem is introduced. The GEO satellite observation planning problem includes a GEO satellite and several targets on earth to be visited. The aim of GEO satellite observation planning problem is to find an observation plan with lowest cost and highest profit. To solve this problem, a NSGA II based algorithm and a Multi Objective Travelling Salesman Problem (MOTSP) model are implemented. In this paper, we extend this problem in several directions: a) in PVRPTW-SC problem, multi trips in a planning horizon are considered; b) time window constraint is considered; c) a changeable visit frequency of each customer in planning horizon is considered.