Scribd Logo
Upload

Welcome to Scribd!

  • 190 views

    Clark and Wright Algorithm

    Uploaded by

    DrPeter de Barcelona
    The Clark-Wright algorithm is used to optimize vehicle routes by minimizing distance traveled. It involves: 1. Developing a net savings matrix using distance and route data. 2. Iteratively selecting the highest value in the matrix that satisfies assumptions to reroute trips, updating the matrix each time. 3. Repeating step 2 until the most efficient route is determined. By applying the algorithm to sample distance and route data, the original 26 mile route is optimized to 15 miles by rerouting trips between locations.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as DOC, PDF, TXT or read online from Scribd

    Clark and Wright Algorithm

    Uploaded by

    DrPeter de Barcelona
    190 views8 pages
    The Clark-Wright algorithm is used to optimize vehicle routes by minimizing distance traveled. It involves: 1. Developing a net savings matrix using distance and route data. 2. Iteratively selecting the highest value in the matrix that satisfies assumptions to reroute trips, updating the matrix each time. 3. Repeating step 2 until the most efficient route is determined. By applying the algorithm to sample distance and route data, the original 26 mile route is optimized to 15 miles by rerouting trips between locations.

    Original Description:

    Example how to use the Clark and Wright algorithm.

    Original Title

    Clark and Wright algorithm

    Copyright

    © Attribution Non-Commercial (BY-NC)

    Available Formats

    DOC, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The Clark-Wright algorithm is used to optimize vehicle routes by minimizing distance traveled. It involves: 1. Developing a net savings matrix using distance and route data. 2. Iteratively selecting the highest value in the matrix that satisfies assumptions to reroute trips, updating the matrix each time. 3. Repeating step 2 until the most efficient route is determined. By applying the algorithm to sample distance and route data, the original 26 mile route is optimized to 15 miles by rerouting trips between locations.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as DOC, PDF, TXT or read online from Scribd
    Download as doc, pdf, or txt
    190 views8 pages

    Clark and Wright Algorithm

    Uploaded by

    DrPeter de Barcelona
    The Clark-Wright algorithm is used to optimize vehicle routes by minimizing distance traveled. It involves: 1. Developing a net savings matrix using distance and route data. 2. Iteratively selecting the highest value in the matrix that satisfies assumptions to reroute trips, updating the matrix each time. 3. Repeating step 2 until the most efficient route is determined. By applying the algorithm to sample distance and route data, the original 26 mile route is optimized to 15 miles by rerouting trips between locations.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as DOC, PDF, TXT or read online from Scribd
    Download as doc, pdf, or txt
    You are on page 1of 8

    Clark-Wright Algorithm

    1. You will be given the following information (in diagram or in table format).

    2 4

    0 1 2 3

    1 3

    2 3 3

    3 4 4 5

    4 3 6 8 2

    This table above is called the _________________________________

    2. Develop the Net Savings Matrix 0 1 2 3 1 .. 2 . . 3 3 . . 4 ..

    Net Savings of going 0 to 1 to 2 to 0 (rather than 0 to 1 and 0 to 2 and back to 0) is: = D0i + D0j Dij = 3+33 =3 Distance between 0 and 1 = D0i = D01 = 3 Distance between 0 and 2 = D0j = D02 = 3 Distance between 1 and 2 = Dij = D12 = 3

    0 1 2 3

    1 ..

    2 . . 3

    3 . . 3 2

    4 .. 0 0 5

    Net Savings per Route 1 to 3 1 to 4 2 to 3 2 to 4 3 to 4 3+44=3 3+36=0 3+45=2 3 + 3 8 = -2 or 0 4 + 3 -2 = 5

    This table above is called the _________________________________

    3. Run the Optimization A) Start with the most inefficient route 3 + 3 + 3 + 3 + 4 + 4 + 3 + 3 = 26 miles

    4 4

    a. Original Net Savings Matrix with the bold values being the original T values.

    1 0 1 2 3
    2

    2
    2 3

    3
    2 3 2

    4
    2 0 0 5

    b. Find the highest number on the Net Savings Matrix and see if the route satisfies our assumptions. Route 3 to 4 has a savings of 5 miles if we dont go back to the warehouse.

    Does it meet the assumptions? 1st Assumption is that the D0i and D0j do not have a T value of 0 Answer: This is true. In this model, D03 currently has T = 2 and D04 has T = 2 2nd Assumption is that D0i and D0j are not on the same path Answer: This is true. Reroute the original trip from: 0 3 0 4 - 0 to: 0 3 4 0

    2 4

    c. Update the Net Savings table with the new T value

    1 0 1 2 3
    2

    2
    2 3

    3
    2 3 2

    4
    2 0 0 1

    B)

    Go to the next highest value on the Net Savings Matrix. It is 3 (doesnt matter which 3 you choose)

    1 0 1 2 3
    2

    2
    2 3

    3
    2 3 2

    4
    2 0 0 1

    Does it meet the assumptions? 1st Assumption is that the D0i and D0j do not have a T value of 0 Answer: This is true. In this model, D01 currently has T = 2 and D02 has T = 2 2nd Assumption is that D01 and D02 are not on the same path Answer: This is true. Reroute the original trip from: 0 1 0 2 - 0 to: 0 1 2 0

    2 4

    a. Update the Net Savings table with the new T value

    1 0 1 2 3
    2

    2
    2 1

    3
    2 3 2

    4
    2 0 0 1

    C)

    Go to the next highest value on the Net Savings Matrix. It is 3 (trips between 1 and 3).

    1 0 1 2 3
    2

    2
    2 1

    3
    2 3 2

    4
    2 0 0 1

    Does it meet the assumptions? 1st Assumption is that the D0i and D0j do not have a T value of 0 Answer: This is true. In this model, D01 currently has T = 1 and D03 has T = 1 2nd Assumption is that D01 and D02 are not on the same path Answer: This is true. Reroute the original trip from: 0 1 0 3 - 0 to: 0 1 3 0

    2 4

    a. Update the Net Savings table with the new T value

    1 0 1 2 3
    2

    2
    2 1

    3
    2 1 2

    4
    2 0 0 1

    Now, take a look at the model. We can eliminate the trip between 0 and 3 because it serves no purpose. The most efficient route becomes 0 2 1 3 4 0 or 3 + 3 + 4 + 2 + 3 = 15 miles

    2 4

    You might also like