A Mathematical Optimization Model for the Multi-Objective Sweep Based M-VRPSTW

Abstract

Good transportation systems are often described as those satisfying several quality factors, such as minimum cost, minimum time and/or minimum distance.  However, there are many issues that affect the efficiency of transportation of goods.  In the case of vehicle routing with hard time windows (VRPHTW or simply VRPTW), service may not be able to take place if the vehicles arrive at customers beyond their latest time for service.  Thus, introducing soft time windows where hard time windows for service may be violated with some penalty costs may provide an alternative that is more suitable in terms of applicability, practicality and costs savings.  In past VRPSTW studies, unlimited number of vehicles is assumed when solving.  However, in real practice, companies only have limited number of vehicles.  Thus, in this study, limited number of vehicles is introduced on the VRPSTW (m-VRPSTW).  The objectives of this study are to formulate new bounds for the time windows for depot’s and customers’ service, to define the penalty costs function models for early and late arrivals, to formulate a 0-1 Integer Programming model for the m-VRPSTW and to solve the model by using the Sweep Heuristics and Genetic Algorithm approach.  The Binary Integer Programming model is formulated to solve m-VRPSTW with three objectives functions which are to maximize the total number of customers served, to minimize the number of vehicles used and to minimize the total traveling cost.  Solomon benchmark instances has been used in the computational experiments for tests using different number of vehicles. The model was solved by using MATLAB Optimization Tool Box.  Feasible solutions are found for them-VRPSTW model.  Results based on the m-VRPSTW model are presented and compared with the VRPSTW model of unlimited number of vehicles. The best results are selected based on the following criteria: minimum total schedule time (TST), minimum average waiting time and minimum average penalty cost incurred.  Further refinement on model and solution method is recommended to improve the solution quality.