Zaman çerçeveli araç rotalama problemi ve yer bulma-rotalama problemi için algoritmalar

In this thesis we study two well-known routing problems. In the first, we solve thevehicle routing problem with time windows (VRPTW). The VRPTW involves designinga set of routes to serve all the customers without violating the capacity of vehicles andtime windows constraints of the customers. We present a new branch-and-cut algorithmfor solving the VRPTW. We apply a separation routine that detects all cycles in the nodesof the branch-and-cut tree in polynomial time and then tries to eliminate these cycles bychecking the violated valid inequalities. A new branching strategy that branches on thecycles found in the node relaxations of the MILP model is also introduced.Computational experiments are performed on the Solomon test problems. So far the mostsuccessful exact algorithms for the VRPTW applied shortest path decomposition to theproblem. When the proposed algorithm is compared with the other algorithms in theliterature, it has been shown that decomposition based exact algorithms (i.e., columngeneration, Lagrangean relaxation) do not perform the best for the entire Solomon testproblems, the performance of the proposed algorithm is better than decomposition basedexact approaches on the long horizon test problems.The second problem studied is the location-routing problem (LRP). The LRPconsists of selecting a subset of locations among given candidate facility locations anddetermining the vehicle routes to visit all the customers from the selected facilitylocations. We propose a column generation algorithm for the solution of the capacitatedlocation-routing problem in which we have multiple capacitated facilities and vehicles.The master problem in our column generation algorithm is a set-partition basedformulation which proved to be useful for a variety of routing problems such as thevehicle routing problem with time windows. For the pricing subproblem we solve theelementary shortest path problem with resource constraints (ESPPRC). The resultingalgorithm is tested on various LRP benchmark problems. The proposed columngeneration algorithm gives tight gaps for most of the benchmarks.