GraphHopper.com | Forum | GitHub | Maps | Blog

Negative values as capacities


#1

Is there a way to alleviate current load size of vehicles as the route progresses in a services problem? In shipment, a pickup increases while drop off decreases, but in services I cannot find such feature.

I’m trying to avoid moving my problem to shipments due to the fact that the loading stations do not share a common or known location, they are spread across the map.

Thanks in advance


#2

Currently a service is effectively a pickup (when it has positive capacity). For your case, perhaps you can try just modeling a job as a delivery instead of a service/pickup.

You can find a list of job types that jsprit can currently model here:


#3

Wow, I was not aware I could use them like this. Thank you so much


#4

Btw, they have been actively working on job refactoring recently, so things might change.

You can check out the branch here:


#5

Are there any docs available from the refactor until now?


#6

I guess they don’t have a good doc for now, but you can check out their discussions here:

and all the pull request made by @Balage1551:


#7

Sorry, I had some other tasks to do, but will start a migration documentation as soon as I could.


#8

Awesome to hear it, thanks guys. I’ll check first the pull requests.


#9

@Balage1551 I am going to help. Let us plan the new release for the beginning of next year.


#10

@stefan: Good idea. As for now, it looks like I’ll have a little lighter work on January.


#11

I tried using the approach provided by jie31best and found it breaks under certain circumstances.

A delivery activity can be appear at the start of the route even if no pickup has been assigned yet, effectively delivering nothing.

If I have two pickups with size 2, a delivery with also size 2, and the vehicle has capacity of 2. The expected behavior is that it will pickup, deliver, pickup.

The actual behavior is delivery, pickup. Leaving the other pickup unassigned. No there constraints were applied.

Is this expected behavior, or should I create a constraint that deals with this. If the latter, should it be hard or soft? (I always pick the wrong one)


#12

Hi @aj1310,

Jsprit assumes Delivery jobs are already loaded at the very beginning of the route, and Pickup jobs are not unloaded until the end of the route, as I explained in this post.

Therefore, in your case, the vehicle has to unload the Delivery job before it can load one Pickup job and is not able to load the second Pickup job, due to the capacity constraint.

Best regards,
He

EDIT:
btw, if you would like to model a job that something is to be loaded and then unloaded during the route, you should model it as a Shipment.


#13

I would use Shipments but a specific pickup does not map one-to-one with a delivery. An X number of pickups could be 5 “newspapers” depots across town that would have to be delivered to 5X houses. So pickups and deliveries must not have a direct relationship.

What I’m trying to accomplish is a vehicle has a max capacity 100, but starts with a, let’s say, 60 initial capacity. So it could accomplish these cases depending on the problem:

Increase 40 units of jobs, whether the job is a pickup, or pickupShipment.
Decrease 60 units of jobs, whether the job is a delivery, or deliveryShipment.
Or a mix of all these.

If I would implement this, would I have to recreate the capacity constraint or is there some other way I’m missing?


#14

hmm, if you have activities with relations more complicated than the one-to-one as in a shipment, I guess you can model them as individual service/pickup/delivery jobs, and use hard/soft activity/route constraints to enforce the relations you want.

You can refer to the classic stackoverflow post on related job in jsprit:

Perhaps in the future the refactored job could make things easier.

Best regards,
He


#15

I’m trying to restrict that the load ever tries to go down from 0 at any step of the route, a constraint would prevent the insertion. I’m using the internal states to keep track of the load, but there are some I don’t understand:

MAXLOAD
LOAD
FUTURE_MAXLOAD
PAST_MAXLOAD

At the moment, it works with start and services. But at the moment of dealing with shipments. The code fails.

    val previousMaxLoad = if (prevAct is Start) {
      stateManager.getRouteState(iFacts.route, InternalStates.LOAD_AT_BEGINNING, Capacity::class.java)
    } else {
      stateManager.getActivityState(prevAct, InternalStates.PAST_MAXLOAD, Capacity::class.java)
    } ?: NegativeLoadDelayConstraint.defaultCapacity
    val futureMaxLoad = if (prevAct is Start) {
      stateManager.getRouteState(iFacts.route, InternalStates.MAXLOAD, Capacity::class.java)
    } else {
      stateManager.getActivityState(prevAct, InternalStates.FUTURE_MAXLOAD, Capacity::class.java)
    } ?: NegativeLoadDelayConstraint.defaultCapacity
    val currentRoute = iFacts.route.activities.map { it as? TourActivity.JobActivity }.map { it?.job?.id }.joinToString(",")
    if (!previousMaxLoad.isGreaterOrEqual(Capacity.defaultCapacity)) {
      return HardActivityConstraint.ConstraintsStatus.NOT_FULFILLED_BREAK
    }
    if (!futureMaxLoad.isGreaterOrEqual(Capacity.defaultCapacity)) {
      return HardActivityConstraint.ConstraintsStatus.NOT_FULFILLED_BREAK
    }
    if (!Capacity.addup(previousMaxLoad, newAct.size).isGreaterOrEqual(Capacity.defaultCapacity)) {
      return HardActivityConstraint.ConstraintsStatus.NOT_FULFILLED
    }
    if (!Capacity.addup(futureMaxLoad, newAct.size).isGreaterOrEqual(Capacity.defaultCapacity)) {
      return HardActivityConstraint.ConstraintsStatus.NOT_FULFILLED
    }
    return HardActivityConstraint.ConstraintsStatus.FULFILLED

Any idea of what could be wrong?