The Travelling Salesman Problem: Vehicle Routing Problem

Improved Essays
One of the key functions in logistics systems is physical distribution, involving the flow of products from manufacturing plants or central depots through the transportation network to consumers. It is an expensive function, especially for the industries involving distribution. The Operational Research literature has addressed this problem by calling it as the vehicle routing problem (VRP). Vehicle scheduling or vehicle routing problem (VRP) is a combinatorial optimization and integer programming problem. The Travelling Salesman Problem (TSP) was introduced much before the Vehicle Routing Problem(VRP). In a way, VRP generalises the TSP.
VRP first appeared in a paper by George Dantzig and John Ramser (1959), in which first algorithmic approach
…show more content…
n) are available and loads qj are required to be delivered to points Pj (j= 1... M) from a depot Po. Given the distances d, between all such points it is required to minimize the total distance covered by the trucks. For convenience of computation Ci are ordered such that Ci-1 < Ci (I = 2…n) and it is assumed that Ci<<∑qj (j = 1…m) Since in the solution some trucks may only be partially loaded, xi needs to be sufficiently large to ensure that all loads are allocated. For purposes of computation it is therefore made infinite. It might be noted that if Cn≥ ∑qj (j = 1…m) then the problem becomes the traveling salesman problem. The Dantzig and Ramser method focuses only on the state C2= C3= ... Cn = 0 Due to the restriction that, in the first of N stages, only customers whose combined load does not exceed C1/2N-1 are permitted to be linked, points may be linked that are far apart, and may be virtually on opposite ends of a straight line through the depot. Although obviously long links may be excluded in the initial stages by 'rapid corrections,' when two points become linked in an 'aggregation' they remain aggregated. As a result, this method tends to lay more emphasis on filling trucks to near capacity than on minimizing distance. The distance table in the Nth stage could require each cell to contain the shortest distance from the depot through 2N points, i.e., the 'traveling salesman …show more content…
Each customer is serviced exactly once and, furthermore, all the customers must be assigned to vehicles without exceeding vehicle capacities (Bodin et al. 1983). In the vehicle routing and scheduling problem with time window constraints (VRSPTW), these issues must be addressed under the added complexity of allowable delivery times, or time windows, stemming from the fact that some customers impose delivery deadlines and earliest-delivery-time constraint. In the presence of time windows, the total routing and scheduling costs include not only the total travel distance and time costs considered for routing problems, but also the cost of waiting time incurred when a vehicle arrives too early at a customer location or when the vehicle is loaded or unloaded. The VRSPTW has emerged as an important area for progress in handling realistic complications and generalizations of the basic routing model (Schrage 1981, Bodin et al.). Time windows arise naturally in problems faced by business organizations that work on fixed time schedules. Specific examples include bank deliveries, postal deliveries, industrial refuse col- lection, dial-a-ride service, and school bus routing and scheduling. So far, this type of constraint has been handled in an ad hoc manner, mostly by

Related Documents

  • Decent Essays

    Nt1310 Unit 6 Project

    • 496 Words
    • 2 Pages

    Each scenario was run with 20 replications to account for the variability within the model. We averaged the maximum cumulative square footage for each month from all the replications for each scenario and analyzed a total of 27 data tables for this project. Each variant has multiple data tables and graphs based on the part type: loose parts, individual dollies, and totes. Each of these variants and part types has data for each of the three delivery rules: delivery on the first day of the station, delivering parts two days before the station starts, and delivering parts three days before their scheduled installation. These graphs provide a visual representation of the maximum square footage required for staging parts at any point in time over the course of the four year production rate transition.…

    • 496 Words
    • 2 Pages
    Decent Essays
  • Decent Essays

    The trucking industry has gone through, and continues to go through, some of the most difficult times since the Motor Carrier Regulatory Reform and Modernization Act of 1980. There are five key events that are occurring simultaneously: skyrocketing fuel prices, major reductions in economic activity, massively changing supply chains, falling US dollar, significant pockets of debt secured by trucking assets. The rapid increases in the price for fuel can have been causing a delayed and devastating effect on freight management companies. With the sudden fall of fuel cost, it could result in short-term boosts in profit and a surge of competition within the market to provide consumers with the lowest price.…

    • 111 Words
    • 1 Pages
    Decent Essays
  • Improved Essays

    Jos A Bank Case Study

    • 2526 Words
    • 11 Pages

    Identify key production planning considerations (which, when and how much of each to produce, methods of dealing with short/long term changes in capacity demand). Carrier Corporation had about 200 distributor locations for their furnaces. They used a just-in-time manufacturing system. Some distributors placed monthly orders and some weekly. 15 to 50 percent of their orders had an “at once” delivery requirement meaning they were needed within 30 days; the rest were greater than 30 day orders.…

    • 2526 Words
    • 11 Pages
    Improved Essays
  • Improved Essays

    Hrm 531 Week 9 Final Paper

    • 1404 Words
    • 6 Pages

    The United Parcel Service operation is affected by governmental action and political challenges and therefore, determine the company’s financial standing through opportunities and threats. A direct implication is through the transportation operating costs provided to customers. The courier company allocates shipping expenses among big competitors such as Federal Express (FedEx) and DHL. The government creates the rules and dictates to a certain extent the standards of each competitors. Periodically, the government will modify these rules and standards convincing companies to change the way they work.…

    • 1404 Words
    • 6 Pages
    Improved Essays
  • Decent Essays

    Tlmt51 Career Paper

    • 282 Words
    • 2 Pages

    Through this method it has multiple resources I can choose from which I have chosen TLMT525 Research Methods in Transportation and Logistics Management by Maryelizabeth Gano, also the APUS CampusGuides (htt://apus.libguides.com/TLMT525). This source contained information…

    • 282 Words
    • 2 Pages
    Decent Essays
  • Decent Essays

    2. (10 pts.) Referring to the table below, hiring a driver costs $10. Each machine costs $100. Which method should he use and why?…

    • 289 Words
    • 2 Pages
    Decent Essays
  • Improved Essays

    Regulatory Compliance

    • 499 Words
    • 2 Pages

    Variety of Solutions Depending upon the type of business you operate, the type and number of trucks and trailers you need…

    • 499 Words
    • 2 Pages
    Improved Essays
  • Great Essays

    b) The second strategy that may be embraced is the improvement of the percentage of load miles in their fleet. This move is aimed at ensuring more effective coordination of the entire freight. This is an external strategy for the profitability of the company and efficiency I it operations(Lane, 2011). Pick up points are well marked, with centralization of operations since all services will be controlled from a central geographical area. The workload will then be minimized for efficiency.…

    • 1090 Words
    • 4 Pages
    Great Essays
  • Decent Essays

    Intermodal Rail Freight rail moves more than 70 percent of the nation’s coal, 58 percent of its raw metal ores, and more than 30 percent of its grain Truckload carriers are expected to increase their use of railroads to handle intermediate and long-distance trailer hauls into the future. On lower value goods, trucks share a dual natured relationship with railroads. They cooperate in providing intermodal services. They also compete to capture market share on goods like automobiles and auto parts, food and kindred products, and intermodal shipments. Weight and distance affect this competition.…

    • 285 Words
    • 2 Pages
    Decent Essays
  • Decent Essays

    Compared to other sources of freight, trucking freight method needs lesser amount of capital. For example, when using rail or air as freight modes, the capital investment that has to be borne by the authorities are much. When using trucking as a freight mode, the cost of constructing, operating and maintaining roads and high ways become much cheaper. Furthermore, freight handling authorities are not liable to construct roads and high ways as they are built by the state and local governments. The only fact that the trucking freight authorities have to do is to pay a certain amount to the state or local government, when they use the roads and high ways (Forkenbrock, 1999, 2001).…

    • 135 Words
    • 1 Pages
    Decent Essays
  • Great Essays

    BSG Lessons Learned How did the key theories and concepts in the course relate to the simulation? The Business Strategy Game (BSG) was the practice of strategic management that offers virtual executive experience. The assigned team could analyze the market, set the direction, and make strategy for company’s growth in BSG.…

    • 1159 Words
    • 5 Pages
    Great Essays
  • Improved Essays

    Haul Trucking

    • 490 Words
    • 2 Pages

    When you have a large piece of equipment, or other heavy cargo, that needs to be shipped to a job site you will likely call a heavy haul trucking company to do the job. They have the right type of trailer, a powerful semi tractor and a qualified driver ready to take care of your load. Before they arrive, however, there are some things that you need to do to ensure that the process is smooth and trouble-free for everyone involved. Loading Procedures Heavy haul trucking companies generally have several types of trailers to choose from. These include lowboys, goosenecks, drop deck trailers, and standard flatbeds.…

    • 490 Words
    • 2 Pages
    Improved Essays
  • Improved Essays

    In an effort to improve supply chain operations, DR Pepper Snapple Group, a maker of soft drinks, created a network of facilities strategically located to supply current and potential future customers (Fuhrman, 2010). These facilities are located in Irving, Texas; Jacksonville, Florida; Aspers, Pennsylvania; and Williamson, New York. The new western distribution hub, their latest addition, is located in Victorville, California (Fuhrman, 2010). The main idea behind the construction of these facilities is to continue production closer to customers in an effort to increase the speed of delivery and reduce costs in the supply chain. Based on their calculations they are capable of covering 80% of the population with these facilities (Fuhrman, 2010).…

    • 375 Words
    • 2 Pages
    Improved Essays
  • Great Essays

    Trans-Shipment Container Management in the Port of Piraeus Theodoros Koromilas ABSTRACT As a mainly trans-shipment container port, the container terminal of the port of Piraeus has as a primary goal to provide equipment and facilities to deliver efficient and professional service. The commercial port of Piraeus consists of three (3) container terminals, of which one (1), Terminal I, is being operated Piraeus Port Authority S.A. (P.P.A) and two (2), Terminal II and III by the Piraeus Container Terminal S.A. (P.C.T.), which is a subsidiary of COSCO Pacific. Head offices are located behind their terminals for each organization.…

    • 1356 Words
    • 6 Pages
    Great Essays
  • Superior Essays

    - Planning product distribution and sales, including the creation, if necessary, the relevant value chains with warehouses and shops, as well as agency…

    • 2159 Words
    • 9 Pages
    Superior Essays