|
|
 |
Vehicle
Routing |
 |
-
Planning Data |
|
|
The Planning Data worksheet
holds data specific to a particular routing problem. The worksheet
is created by clicking the Make Plan button at the
top of the Distance worksheet. The Vehicle Routing
Data dialog accepts data for a plan. A Distance worksheet
may have several plans, but each Planning Data worksheet
is based on a specific Distance worksheet.
A plan has a name that is used to name the worksheet created
at this step. The name is also used to label a variety of named
ranges on the worksheet. The name may contain only alpha-numeric
characters with no spaces or punctuation. It cannot be changed
once the worksheet is created. Four numeric fields define
a plan: the number of deliveries, the number of trucks, the
number of additional trips and the number of resources. All
except the number of resources can be changed after the worksheet
is created. The Random Data checkbox causes the add-in
to insert random data into some of the data fields. The data
can be changed later to represent an actual situation.
The dialog accepts the number of deliveries to be made and
the number of individual vehicles (called trucks)
used to make the deliveries. A truck begins its route (or
trip) at a particular location from Distance worksheet
called the depot.
A trip begins and ends at the depot. Different trucks
may serve their routes simultaneously. For an additional trip
a truck truck returns to the depot, picks up another set of
deliveries. After the trip, the truck returns again
to the depot. A single truck makes two or more trips
sequentially.
Deliveries may use truck resources such as space or weight.
Our example uses a single resource called capacity. Each delivery requires one unit of capacity (capacity utilized
is called load) and the default value of the truck
capacity is the number of deliveries divided by the number
of trucks rounded up to the nearest integer. For example two
trucks making 10 deliveries will each have a capacity of 5.
An example plan is shown below. We discuss the various data
items below the figure. Click picture to open a window with
a larger image |
|
| |
The data has three parts: the
parameters at the top, the truck and trip data starting in
row 11, and the delivery data staring in row 18. The parameters
in column N define three constants related to distance.
N2 prescribes the cost per unit distance measure. For the example,
we assume the cost measure is dollars and the distance measure
is mile, so the example shows $1.50 per mile. The entry in
N3 is the time required for distances traveled between locations
on the Distance worksheet. If we measure time in minutes,
the example specifies 3 minutes per mile (20 miles an hour)
for travel between locations.
(If the distances matrix holds travel times, we would use 1
for this parameter.) N4 shows the time required for each unit
of distance traveled from a map location to the site of a delivery.
We call this the local distance. The example shows 5 minutes
per mile or 12 miles an hour. This assumes travel between
locations defined on the Distance worksheet
is faster than local travel.
The resource data starting in column Q gives the names for
the resources when applied to trucks, the names for deliveries,
and the penalties for using more resource than is available.
When a single resource is specified, the default names are capacity and load.
The penalty of 1000 is used by the optimization to penalize violations
of the resource constraint. One might increase or decrease this
number depending on the flexibility of the resource.
The truck and delivery data have similar columns. All the data
in these columns may be set by the user except the yellow field
called Local Distance. This field is computed with Excel
formulas. The data reflects the cost model for the problem. |
| |
| Name |
The default names are assigned as in the example,
but can be changed to identify specific vehicles and delivery
points. The example has no additional trips, but when they
are included they are named Trip 3, Trip 4. The
index assigned to the first additional trip is one greater
than the number of trucks. |
| Depot Time or Delivery Time |
This is the fixed time to load a truck or make a delivery.
The time that a truck leaves the site is the arrival time
plus the delivery (depot) time. |
| Ready Time |
This is the earliest time that a particular trip may start
or that a particular site will accept a delivery. This is
a hard constraint. If a truck reaches a site before the ready
time, it must wait to begin the delivery process. For trucks
or trips, the time will indicate the earliest time the truck
or trip may begin. |
| Early Time |
The is a scheduled earliest time for a truck to arrive
at a delivery site. The truck may arrive before this time,
but a penalty will be assessed. The early time differs from
the ready time in that the early time constraint may be violated,
but at a penalty, while the ready time constraint is never
violated by a solution. |
| Late Time |
The is a scheduled latest time for a truck to leave a
delivery site. The truck may leave after this time, but a
penalty will be assessed. A truck leaves a site at the arrival
time plus the delivery (or depot) time. |
| Duration Penalty |
When a truck leaves a site, the solution is assessed a
cost that is the duration penalty multiplied by the leaving
time. This parameter can reflect priorities with sites having
greater duration penalties for the higher priorities. |
| Early Penalty |
When a truck arrives at a site before the early time, the
solution is assessed a cost that is the early penalty
multiplied by the difference between the early time and the
arrival time. When a truck arrives after the early time,
no penalty is charged. |
| Late Penalty |
When a truck leaves a site after the late time, the
solution is assessed a cost that is the late penalty multiplied
by the difference between the leaving time and the late
time. When a truck leaves before the late time, no penalty
is charged. |
| Capacity/Load |
The first resource constraint is automatically named the
capacity. The capacity of a truck is used by the loads associated
with the delivery sites. The default load for each site is
1 and the default capacity of each truck is the total load
divided by the number of trips rounded to the next integer.
Capacities may reflect any limitation on trucks
and multiple resources may be defined. Each will receive
a column for data on the plan. |
| Map Location |
This is the map location chosen from the Distance worksheet
that is closest to the delivery site or truck depot. With
random data the values are assigned randomly. Trips always
begin and end at the depot. The default location of the depot
has the greatest index. If a location of 0 is assigned the
site or trip is left out of the plan. |
| x and y coordinates |
These are the coordinates of the delivery sites. Initially
a formula links these values to the map locations for easy
assignment of coordinates to delivery sites. The coordinates
may be assigned different values than the map locations for
greater accuracy. Thus the depot and delivery sites may have
locations different than the map locations. |
| Local Distance |
This is the Euclidean distance between the assigned map
coordinates and the delivery site coordinates. When travel
takes place from one site to another, the trip is assumed
to be the map distance between the
two sites plus the sum of the two local distances. Both local
distance and the distance between map locations is assessed
cost at the rate specified by the cost/distance parameter. |
|
| |
The information entered on the Data worksheet
defines the set of the deliveries required for some interval
of time, perhaps a day of operation. The add-in tries to develop
a schedule that will meet the delivery requirements with the
trucks and the trips provided. The criteria is a composite cost
that includes the cost for travel, the total duration penalties,
the total early and late penalties, and the total resource violation
penalties. The model involves both time and distance as will
be reflected on the model worksheet. |
Changes |
| |
Once constructed, the number of
deliveries, the number of trucks and the number of trips may
be changed using the Change button.
The dialog below specifies the number of deliveries to be added
or deleted. To change the number of trucks or trips specify
new values in the associated fields.
|
Buttons |
| |
At the top of the page there are
several buttons.
The Distance Worksheet button makes
the distance worksheet active. Each plan has a unique associated
distance worksheet. The Change Data button allows
changes in the plan. All features of the model can be changed
except the number of resources. The Assign Locations button
determines the closest map location to each delivery or depot
location. This is useful when the plan is given coordinates
for each delivery site that are different than the map locations.
The Make Model button constructs the model and results worksheets
discussed on the following pages. |
| |
|
|
