Algorithmic comparisons for a vehicle assignment problem

The traveling salesman problem (TSP) is a problem in which a traveler must traverse a set of completely connected cities using the minimum length cycle. This problem is at the root of the vehicle routing problem (VRP). The VRP refers to a capacitated version of the TSP. A fleet of vehicles is available to service terminals. A shipment size is associated with each movement load, and each arc has an associated cost. The objective is to minimize the total cost, while ensuring that all goods have met their service commitment.; A linear program (LP) is a problem that can be expressed as; Minimize cx; Subject to Ax=b; x>=0.; The importance of linear programming in many applications is the existence of good techniques for finding optimal solutions. Reklaitis, et al. (1983) states that in practice, many LP problems require integer solutions for some of the variables. The phrase (linear) integer programming (IP) refers to the class of LP problems where some or all of the decision variables are required to be integers. IP's are often more realistic than LP's, but much more time-consuming and difficult to solve.; This thesis will describe various techniques used to solve a VRP for a transportation company. This company (‘Company A’) must move goods to distribution centers, where the goods will be sorted and sent out for delivery. Solving the VRP means better utilization of the network and a positive effect to the bottom line.