Route Optimization with Multiple Depots, Job Types and Destinations

Question

I am new to route optimization and would appreciate your help in solving the following business requirement using jsprit. I got some feedback from Stefan Schröder who helped me to learn some basics about jsprit. I will explain the business requirement first then ask few questions.

The objective is to schedule a list of maintenance jobs that need to be completed in a month. A daily schedule would need to be prepared for the entire month. The objective here is to perform maximum number of jobs per day.

• There are 4 depots each one in a region
• Each region has around 70 warehouses for a total of 300 warehouses
• The distances between each depot and warehouses within that region are known
• There are 3-4 vehicles of different types at each region for a total of 12 vehicles
• Vehicles within a region can only serve warehouses within that region
• Vehicles within a region have the same start point which happens to be the end point
• Vehicles do not have any capacity, pickup or delivery requirements
• Vehicles are used only to transport workers who will perform the maintenance jobs
• The average speed of each vehicle is known
• There are roughly 80 maintenance job types
• Each job type take a known amount of time in minutes
• A maintenance job does not have to start at a specific time
• On a monthly basis, there are around 200 maintenance jobs that need to be performed
• These jobs could be at any warehouse
• More than one job could take place at the same warehouse on the same day or different day
• There are 3 eight hour shifts within a day. 6AM-2PM, 2PM-10PM and 10PM to 6AM
• A vehicle would leave the depot warehouse at the start of the shift and visit as many warehouses within the eight hour shift
• A vehicle has to wait at the warehouse while the job is being performed before moving to the next warehouse or return to the depot warehouse

My basic understanding is that a maintenance job can be defined as a service in jsprit and that the start/return time can be set for each vehicle. Also, a cost matrix can be used to add time and distance to the relationship between vehicle and warehouses. The questions I have are:

1. Each maintenance job would need to be defined as a service, as a result there will be 200 service objects that are passed to the VRP solver, correct?
2. The VehicleTypeImpl has addCapacityDimension(), setCostPerDistance() and setCostPerTime() method. What exactly are these and how do they apply the above case?
3. The Service.Builder has addSizeDimension() method. What does it do?
4. The costMatrixBuilder has method to add TransportDistance and TransportTime. Which units are used by these methods and how can I used them?
5. For each depot, a Coordinate would need to be defined and passed to setStartLocationCoordinate() method for each VehicleImpl. Is this right?
6. The vehicleBuilder has setLatestArrival( double maxDuration); which unit is used here?

I do appreciate any help in solving the above case.

Thanks, Adam

EDIT1:

Few questions

A. The setEarliestStart() and setLatestArrival() methods accepts double value, how can I specify the earliest departure and latest arrival as actual Date to these methods? For instance, start time is November 28, 2014 at 2PM and end time is 10PM on the same day.

B. Is there a way to specify the service time in minutes?

C. The VehicleTypeImpl.Builder.setMaxVelocity(double inMeterPerSeconds) method expects the maximum velocity, is there a way to specify the average speed of the vehicle?

D. All vehicles have to work on the three shifts; does this mean I will have to define the same vehicle three times, one for each shift with various earliest departure and latest arrival times?

E. As the jobs can be performed any time during the month, would the time window for each job be passed as begin and end of month to Service.Builder.setTimeWindow() method?

Answer 1

ad1) correct

ad2) If capacity does not play a role, you do not need addCapacityDimension(..). if it does, you can use this method to define an arbitrary number of capacity dimensions, such as for example weight, volume, number of pallets (which are three dimensions then). With .setCostPerDistance(..) you set - as the name suggests - the cost per distance unit (e.g. 1€/km). Accordingly, with .setCostPerTime(..) you set the costs per time unit, e.g. 20€/hour. Thus, if your vehicle/driver traveled 100 km in 1 hour, it would cost 100 km * 1 €/km + 20€/hour * 1 hour.

ad3) Services might consume capacity in your vehicles. A service might be referred to the pickup of freight at the customer/service site. It might have a certain volume, weight and it can be loaded onto a certain no. of pallets. This is what you define with .addCapacityDimension(..)

ad4) You define the units. It should be the same unit, you assume when you set the cost parameters.

ad5) Correct. But you do not neccessarily need coordinates. You either need a locationId or a coordinate, but you can set both. The locationId should be the same you use when adding your time and distance relations to the costMatrix.

ad6) Again, you determine the unit.