A study on multi-trip vehicle routing problem with time windows and meal break considerations

Abstract

In the manpower scheduling problem with multiple trips vehicle routing and time windows consideration, a group of staff workers has to be assigned to a number of jobs in such a way that the total number of staff required is minimised, and each job’s requirements for manpower, transportation time, and time windows must be respected. Furthermore, if several staff is requested to cooperate, they must work on the job at the same time. The problem originates from manpower scheduling for the in-flight food loading operations and could be modeled as Multiple Trips Vehicle Routing and Scheduling Problem with Time Windows and meal break considerations (MTVRSPTW-MB). In this thesis, we present a mathematical model of MTVRSPTW-MB and show that even for a reduced problem; it is intractable on this small sample size of data. Therefore, we developed an original two-stage scheduling heuristic algorithm to cope with this complicated combinatorial optimisation problem. This heuristic uses some simple laxity scheduling and priority rules to do the job assignment and scheduling in two stages. The heuristic is tested on real-life problem instances supplied by one of the in-flight caterers from Malaysia. On top of that, a pre-processing data algorithm was developed to spread the demand as evenly as possible. We obtained excellent solutions in reduction manpower in all the cases within three seconds. We also evaluated the heuristic further by comparing it with a popular heuristic insertion algorithm. The computational results report the effectiveness and robustness of our proposed heuristics. Our heuristic algorithm has also proved computational bounded.