Vehicle scheduling problem with sequence dependent trips

In this study, we consider a vehicle scheduling problem with sequence dependent trip times. The problem is assigning vehicles to a set of trips with fixed ready times and deadlines, while minimizing cost. The trip time for a vehicle between any two places is also known deterministically. A number of different types of vehicles are available for transportation, each with different capacities, fixed and variable costs. The costs for regular and overtime utilization also vary for different types of vehicles. The problem resembles the Tactical Fixed Job Scheduling Problem where ready times and deadlines of jobs are known in advance, and the objective is to minimize the cost of machines to perform all the jobs. A job cannot be processed unless a machine is available at its ready time. The problem is formulated as an Integer Programming Model. A spread time constraint determines the regular time usage of the vehicles. The formulation is coded in LINGO 8.0 and GAMS 20.2 with CPLEX solver. Due to the complex nature of the problem, it is observed that the optimal solution of even middle-size instances is very time consuming. Hence, we develop three different heuristic approaches for the problem, each one having two different types based on overtime usage allowances. The algorithms are coded in C programmer Language using DEV C++ Compiler. The average behaviour of the algorithms is investigated through computational experiments. Lower bound values for the problem are found using GAMS developing some approaches, and the performances of the algorithms are compared based on these bounds. The problems whose number of trip is more than a hundred have been solved in a very short time. The least solution of heuristic approaches is actually 10% greater than optimum solution. Key Words: Tactical Fixed Job Scheduling, Spread Time Constraints, Integer Programming, Heuristics.