0

I am looking to model a vehicle routing problem with time windows on OctaPy. Specifically, this problem involves traffic enforcement on public roads, so parking wardens need to survey carparks and road segments and visit them more than once during a 24-hour period.

I refer to the answer in the following question as foundation to develop my problem: Is it possible to create a VRP solution using NetworkX?

I have a few questions regarding the modelling:

  1. How does OctaPy model time-dependency, that is a different edge weight representing travel duration depending on the time of day?
  2. How do I model the demand points if each point needs to be visited X times?
  3. If a demand point is to be visited X times, how can I enforce a time window gap such that the duration between visits is at least a fixed duration (e.g. 1 hour)?
kangsoon93
  • 11
  • 3

1 Answers1

1

  1. OptaPy models time-dependency the way you model time-dependency. That is, whatever you use to model time-dependency (may it be an edge, a list, a matrix, a class, etc.), OptaPy can use it in its constraints.

  2. If X is known in advance, for each demand point, you create X copies of it and put it in the @problem_fact_collection_property field. If X is not known in advance, consider using real-time planning (https://www.optapy.org/docs/latest/repeated-planning/repeated-planning.html#realTimePlanning).

  3. This depends on how you implement your time dependency. This would be easier when OptaPy supports the new VariableListener API for List Variable (as well as the builtin list shadow variables) that OptaPlanner has. Until then, you need to do the calculation in a function. Make Edge a @planning_entity and give it a inverse relation shadow variable (https://www.optapy.org/docs/latest/shadow-variable/shadow-variable.html#bidirectionalVariable). Add a method get_arrival_time(edge) to Vehicle that get the estimated time of visit for a given Edge in its visited_edges_list.

def less_than_one_hour_between(visit_1: Edge, visit_2: Edge):
    visit_1_arrival_time = visit_1.vehicle.get_arrival_time(visit_1)
    visit_2_arrival_time = visit_2.vehicle.get_arrival_time(visit_2)
    duration = visit_2_arrival_time - visit_1_arrival_time
    return timedelta(hours=0) <= duration <= timedelta(hours=1)

def one_hour_between_consecutive_visits(constraint_factory):
    return (
        constraint_factory.for_each(Edge)
            .join(Edge, Joiners.equal(lambda edge: edge.graph_from_node),
                  Joiners.equal(lambda edge: edge.graph_to_node))
            .filter(lambda a, b: a is not b and less_than_one_hour_between(a, b))
            .penalize('less than 1 hour between visits', HardSoftScore.ONE_HARD)
Christopher Chianelli
  • 1,163
  • 1
  • 8
  • 8