135 Reputation

12 years, 77 days

Great idea (and attitude)!...

 >

This is a combinatorial (multi-objective) optimization problem in which the minimization of the following is sought:

(a) No of vehicles

(b) Total travel time

(c) Waiting time

(d) Total distance incurred by the fleet

This is an extension of the classic vehicle routing problem. It accounts for the following features.

Let

V = Fleet of (homogeneous) vehicles

C = Customers (1,2,..., n)

= Cost

= Time (includes service time at customer j)

q = vehicle capacity

Each customer has a time window,

Assume the service time is in direct proportion to the demand at the location

Unused vehicle is modeled by driving the empty route, (0, n+1)

k 2 V

i 2 N

j 2 N

There are two decision variables, namely:

1.

2.

The objective to be minimized is:

 >
 (1)

subject to the following 8 constraints

Each customer is visited once only:

 >
 (2)

The vehicle load limits are defined

 >
 (3)

Each vehicle leaves depot 0

 >
 (4)

After arriving at a customer, the vehicle departs

 >
 (5)

Finally, the vehicle arrives at the depot, n+1

 >
 (6)

Vehicle k cannot arrive at j before

 >
 (7)

The time windows must be observed (assume

 >
 (8)

Integrality constraint

 >
 (9)
 >
 >

Consolidated matrix form...

The use of matrices is really useful here.

Many thanks!

it works now...

That's great!

Thanks for your interest and help.

Reconsidered constraints...

Thanks for your timely response .... much appreciated.

The saga continues ... feasibility toler...

Hi again.

The procedure you sent worked fine.

However, I need to alter the first constraint to account for a realistic situation. This involved switching the order of i and j.  I get an error message to adjust the feasibility tolerance; when I try to do that, I am prompted to alter the depth limit. I have tried various values .... with no luck (worksheet is uploaded).

 >

 >
 >
 (1)

 >

 >

To minimize the objective function, z:

 >

The first constraint is:

 >
 (2)
 >

The second constraint is:

 >

The third constraint is:

 >

The constraints (4 and 5) require binary outputs; zero or one.  This is automatically accounted for, so removed, since all variables will be assumed binary.

Thus, the consolidated constraints are:

 >

The minimized solution is:

 >
 >

Could you suggest any possible fixes?

Many thanks!

Thanks!...

I appreciate the guidance - I'm obliged. I did post the worksheet .... thanks again..

Thanks! It's much appreciated....

Many thanks for the response and effort.

However, the link to the solution is incomplete (I get a blank Word document!).

Would you please re-send the .mws file?

Optimization with binary constraints...

 >
 (1)
 >
 (2)

The distance matrix:

 >
 (3)

The demand array, d:

 >
 (4)

We seek to minimize the objective function, z:

 >
 (5)
 >

The first constraint is:

 >
 >
 (6)

The second constraint is:

 >
 (7)

The thirs constraint is:

 >
 (8)

The following constraints (4 and 5) require binary outputs; zero or one.

 >
 (9)
 >
 (10)

The consolidated constraints are:

 >
 >
 >
 >
 >