Issue in identifying the exact number of vehicles, solution strategy and time limit for VRPDTW problem

[Amarjeet Kumar]

Using OR-tools documentation I have combined CVRP with PD and TW. In this problem, since the pickup at nodes exceeds the vehicle capacity, nodes were duplicated to keep the pickups equal or less than the vehicle capacity and accordingly the O-D matrix is modified. The list of P-D pairs has been taken.  The pickup node has a positive demand and the delivery node has a negative demand. Each node is associated with the service time window. 

There are several things which I am unable to figure out and would require help from the community and experts in this domain. I am listing the doubts I have as of now 

 1. Number of Vehicles

The Approximate number of vehicles is given as input, and different search strategies give different optimal solutions on every run. Solutions either have more vehicles with less objective value or less vehicles with more objective value.  I want the minimum number of vehicles required to complete the VRPDTW, so can we use fixed cost for using a vehicle and how it can be coded?
2. Local Search Strategy and Metaheuristics 

The solutions obtained differs for different combinations of strategies. I want to understand the parameters and the method to evaluate different solution strategies.

3. Time Limit 

How can we understand what time limit needs to be provided to arrive at a solution which cannot be improved for different size of the problem?

 4. Objective Value

Could you please explain how the objective value is calculated? 

Please explain the use of this function and where should i put it in the code 

A vehicle fixed cost - routing.SetFixedCostOfVehicle(FixedCost,vehicle_id)

[Huib Donkers]

1. number of vehicles

To set a fixed cost of a vehicle, use setFixedCostOfVehicle (as you mentioned under "4. objective value").

2. strats/params/config

I'm curious to resources explaining the different options too. My main resource has been the c++ source code (which has some documentation in comments in header files). See e.g. here: https://github.com/google/or-tools/blob/5f7eabb3ffa1de786c224a722f0e9561101c3ab2/ortools/constraint_solver/constraint_solver.h#L435

3. time limit

Maybe you can consider a using search monitor which stops the search based on time spent and quality of the solutions found so far? Sample here: https://github.com/google/or-tools/blob/stable/ortools/constraint_solver/samples/vrp_solution_callback.cc

I think if you don't go too fancy with this, a type of SearchLimit could also be used, but I haven't used them myself. See e.g. https://github.com/google/or-tools/blob/b37d9c786b69128f3505f15beca09e89bf078a89/ortools/constraint_solver/search.cc#L3980

4. objective value

I don't think there's a specific place to put your call to setFixedCostOfVehicle. There are several ways define a cost of something (using a vehicle, transiting between nodes, being late for a time window, etc. etc.), and the sum of all those costs is the objective value. (As far as I understand)

[Amarjeet Kumar]

Thank you so much Huib. I learned how to call the "setFixedCostOfVehicle" function. 

Also thank you for suggesting the search monitor, I am trying to include that. I am not able to figure out whether the search monitor will work if we don't give the search limit for metaheuristics. 

Another thing I wanted to know is whether the objective value is the sum of vehicle travel distance if SetArcCostEvaluatorOfAllVehicles is distance or whether it is the product of some other variables because when I add the distances manually to cross-check, it's less than the objective value.

[Huib Donkers]

About your objective value mismatch, only thing I can think of is that vehicles with empty routes (only start and end) don't contribute to the objective by default, even if the arc cost for the start->end transit is non-zero.

See here: https://groups.google.com/g/or-tools-discuss/c/cla-grYC0rI/m/J5_HESj_AAAJ
The method "ConsiderEmptyRouteCostsForVehicle" has since been renamed to "SetVehicleUsedWhenEmpty"