Hi,
I was getting some odd results with a toy problem where I was testing the fixed vehicle cost. Basically I set it up to only need one vehicle in the solution and it was choosing the one with the very expensive fixed cost, because a waiting cost was ever so slightly cheaper (the difference in waiting cost was much less than the fixed cost difference).
I had a quick look through the code. The relevant code is in JobInsertionConsideringFixCostsCalculator, in the following method:
private double getFixCostContribution(final VehicleRoute currentRoute, final Job jobToInsert, final Vehicle newVehicle) {
Capacity currentMaxLoadInRoute = getCurrentMaxLoadInRoute(currentRoute);
double relFixCost = getDeltaRelativeFixCost(currentRoute, newVehicle, jobToInsert,currentMaxLoadInRoute);
double absFixCost = getDeltaAbsoluteFixCost(currentRoute, newVehicle, jobToInsert,currentMaxLoadInRoute);
double deltaFixCost = (1 - solution_completeness_ratio) * relFixCost + solution_completeness_ratio * absFixCost;
double fixcost_contribution = weight_deltaFixCost * solution_completeness_ratio * deltaFixCost;
return fixcost_contribution;
}
It chooses the wrong vehicle on the very first insert, when the solution_completeness_ratio is 0 (so fixcost_contribution is also zero). I have to confess I don’t understand the equations you’re using here in the fixed cost calculation. I assume you’re doing something to estimate fixed costs early on in the insertion phase, to help guide the insertion better (as opposed to using the fixed cost directly/exactly). Do you have an explanation or reference for the equations here? (If I understand them I might be able to suggest some useful changes).
I’m using the latest release code (1.6.2. I believe).
Hi,
I’m not sure I can follow the logic properly either but there’s a couple of things I notice. solution_completeness_ratio is initialised to 0.5 not zero, which means that on initialisation the relative and absolute fixed costs get equal weighting. Also it appears that the only difference between relative and absolute costs is a scaling mechanism based on the ratio of consumed capacity and available capacity on the vehicle.
It appears that both cost factors will consider waiting time equally (I’m not sure that is the direct cause of this but maybe small changes are enough to tip the balance?), but then there is scaling based on capacity for relative cost. Might there be an inclination then to deploy the largest vehicle if there is not a great difference in fixed costs, but a large difference in capacity? Have you tried setting all capacities equal?
EDIT: If I have actually understood the purpose of the relative fixed cost correctly, then it does make some sense. Balance the absolute fixed cost against the likelihood that later in the solution you are going to have to deploy a more expensive vehicle. But perhaps it’s causing you to fall into a local minima in your particular scenario.
1 Like
The idea is taken from this paper (see page 519):
Dell’Amico, et al.: Heuristic Approaches for the FSMVRP with Time Windows
Transportation Science 41(4), pp. 516–526, © 2007 INFORMS
The determination of marginal fixed costs is simple to calculate and exhibits some inherent “intelligence”, i.e. if a significant share of customers still have to be inserted, vehicles with a low fixed costs per capacity ratio are preferred which usually prefers bigger vehicles. Thus total capacity is expanded. If almost all customers are already in the solution, vehicles with low fixed costs are preferred which in turn prefers smaller vehicles. Thus total capacity is tighten and kept lean, respectively.
@PGWelch Would you mind to share your example so that we can analyse why you get odd results? I wouldnt say that this formular is the answer to everthing 
@roganjosh Thanks for your interpretation 
Let me add some words to your edit: If all jobs are unassigned only relative fixed costs matter. The term converges to “only absolute fixed costs matter” for number_of_unassigned --> 0. Thus later in the solution, the algorithm tries to avoid to add a new expensive vehicle in terms of fixed costs.
Thanks for sharing the paper, and your intro paragraph explains it much more clearly than I did The overall logic is sound to me at least.
I wonder, though, if there’s a fall-down with this approach? The linked paper talks of deliveries… we work with a mix of pickups and deliveries. Therefore, comparing absolute capacity with all jobs that must be done would be highly skewed. What exactly is load in getDeltaRelativeFixCost as I’m trying to piece things together? Is there consideration of pickups and deliveries canceling out when assessing a vehicle (a net assessment)? Is it an assessment of everything or just a handful from the pool of jobs to be done?
Regards,
Josh
Load is here equal to the the maximum load in the vehicle. Let say you have two shipments shipmentA with size 3 and shipmentB with size 6 and the following route: [ start, shipmentA_pickup, shipmentA_delivery, shipmentB_pickup, shipmentB_delivery, end ] then max load is equal to 6. If you have [ start, shipmentA_pickup, shipmentB_pickup, shipmentA_delivery, shipmentB_delivery, end ] then max load is 9.
Does this make sense?
It makes sense to me if you’re looking at a vehicle that has already been bundled into the solution (“What does it have as load already? Can I add more?”) since you mention “route”. On problem initialisation I am lost at what load can mean. From Philip’s issues, it is perhaps possible that initialisation gets stuck in a local minima for one reason or another - how is the initial vehicle selected?
Hi, apologies it’ll be a few days until I have the time available to look into this properly, but briefly speaking this is what seems to be happening…
ConfigureFixCostCalculator.informInsertionStarts sets JobInsertionConsideringFixCostsCalculator.solution_completeness_ratio to 0 before the very first job insertion is made. This then makes the fixed cost contribution zero on the very first job insertion, because of the line:
double fixcost_contribution = weight_deltaFixCost * solution_completeness_ratio * deltaFixCost;
in JobInsertionConsideringFixCostsCalculator/getFixCostContribution. I have 3 vehicles available but only one needs to be used to serve all jobs. One vehicle has a slightly cheaper waiting cost (although a slightly cheaper travel cost or distance cost would create the same problem) but a very large fixed cost (thousands of times greater than the difference in waiting cost could create). The other 2 vehicles have much smaller fixed costs. Because the fixed cost is completely turned off (i.e. is zero) for the first job insertion, the vehicle with the massive fixed cost but slightly cheaper other cost is chosen.
Maybe changing the equation to ensure a minimum non-zero solution_completeness_ratio would fix this? (I would need to read through the paper to advice you better)
Apologies for the lack of self-contained example, I’m running this in ODL Studio which has many layers of code between the Excel input data and calling jsprit…
1 Like
Hi Philip, did you manage to get any further with this? I can confirm your observation that completeness ratio gets set to zero whilst creating the initial route, but then starts at more logical numbers on the actual solution (I guess the damage is done?). I don’t think a specific test-case is needed, I tracked solution_completeness_ratio in my own solution and confirmed it off-the-bat.
@stefan this seems to me like a bug considering how completeness ratio is used elsewhere? It seems that, rather than being more inclined to dispatch larger vehicles initially, it’s almost mandated in solutions that don’t require vehicle swaps at any point…
Sorry @roganjosh no update on this yet. I promise I’ll look into it!
Let me add some words to your edit: If all jobs are unassigned only relative fixed costs matter. The term converges to “only absolute fixed costs matter” for number_of_unassigned --> 0. Thus later in the solution, the algorithm tries to avoid to add a new expensive vehicle in terms of fixed costs.