Tour optimization constraints

[Bernd Welter]

Hi there,

as the tour optimization model seems to be one of the more challenging ones (compared to other PTV APIs such as geocoding) I'd like to provide a special view to the topic which is supposed to help you understanding our model. Therefore I wrote this article about "constraints" in tour optimization. Here we go: usually I define tour optimization as follows from a meta perspective:

• give us a set of orders you'd like to fullfil (aka workload)
• give us a fleet we can utilize for that (aka ressources)
• define the required constraints
• we then let you know "what ressource takes care of which order in what sequence?" and "what are the arrival and departure times?" and more.

And here's the view to the constraints - we offer different categories:

• quantity based :
  • orders may occupy a specific capacity
  • ressources may be able to handle a specific capacity at a time...
• time based
  • opening times at locations (or service start times, to be more precise)
  • drivers availabilities (operating hours)
  • orders may require loading / unloading times
  • break- and rest rules
• skill / equipment
  • orders may require a specific set of equipment or a drivers skill set
  • ressources may offer a set of equipment or skills
  • an order can only be served by a ressource which offers all required skills/equipment
• structural dependencies
  • an order may have to be served as first or last stop on a tour
  • an order of a specific category of goods may not be server with another category of goods at the same time
  • a tour may be enforced to be based on a single trip
  • a tour may be served only by a single depot
  • a customer site can only be approached once within a tour plan
• maximum values :
  • maximum number of customers per tour
  • maximum driving time, travel time, distance
• handling of routing restrictions related to underlying distance matrix:
  • approach customer stop in driving direction
  • acceptance of routing violations / reachability violations
• level of fixation of an (optional) input plan:
  • orders assigned to a specific vehilce can't be shifted to another vehicle
  • a trip that has been assigned to a vehicle can't be shifted to another vehicle and the inner structure of the trip can't be changed (no additional orders, no change of stop sequence)

Some of these restrictions may have to deal with several of the categories at a time, e.g.

• loading patterns are dealing with quanitities and structure
• maximum travel times belongs to maximum values and time based constraints

[clvo]

Hello Bernd,
I have the problem, that I want that all shipments of a customer should be on one stop (and so on one tour). At the moment it happens, that i.e. 3 different trucks drive to the same customer...
So i started searching in the forum and found this article. You write "a customer site can only be approached once within a tour plan"... How can i achieve this? Or do you have an other idea for me?
Thanks a lot!
Claus

[Bernd Welter]

The answer definetly depends on the API of your choice - and maybe I was a bit too optimistic / not sharp enough in my statement:

• PTV Developer Route Optimization Optiflow :
  • check constraints=>tasks=>groups: SAME_ROUTE / CONSECUTIVE (Attention: max number of this constraint is 100 and can easily be exceeded)
  • on location.timeSlot level: maximumAppointments! At least a good approach if there's only a unique timeslot at the location.
• PTV Developer Route Optimization (maintenance mode!) : not supported
• PTV xTourServer2 : check com.ptvgroup.xserver.xtour.PlanToursOptions.singleStopPerCustomerSite