| This thesis presents a solution procedure of a Vehicle Routing Problem with Semi-Hard Resource Constraints where the resource constraints are semi-hard, meaning each resource requirement, such as time window requirements and delivery quantity requirement, can be relaxed to a pre-fixed extent at a predefined cost. The maximum number of customers whose requirements can be relaxed is fixed. This model is useful when the given number of vehicles cannot serve the customers meeting all the requirements without relaxing some constraints, or when relaxation of some of the requirements reduces the overall cost.;This problem is a special case of the VRP with Soft Time Windows, where the violation is restricted to a certain upper bound, and the VRPTW with Multiple Time Windows, where the multiple time windows happen to be adjacent in time. Allowing requirement relaxation complicates the original problem, which is already NP hard. We develop an exact approach to solve the problem with little increase in the computational effort. We use branch cut and price procedure to solve the problem, modeling the pricing problem as an elementary shortest path problem with semi hard resource constraints. The modeling of the subproblem provides a tight lower bound for reduction in computation time. We solve this sub problem using the label setting algorithm, in which we form the labels in a compact way to facilitate incorporation of the resources requirement relaxation information into it, develop extension rules that generate labels with possible relaxation, and develop dominance criteria that reduce the computation time. We apply the concept of look ahead to improve the dual variables. The lower bound is improved by applying the subset-row inequalities. |
