I want to solve a VRP with a column generation algorithm. The objective of the problem is makespan minimization. but there is a point in calculating the arrival time of the vehicle in each node. the vehicle must be synchronized with another transportation mode like a train whose route is predetermined before solving the abovementioned VRP. the train may pass from some nodes that vehicle will pass and in these nodes, the arrival time is maximum of the arrival time of train and vehicle. I want to know how I should solve the pricing subproblem?
5
-
$\begingroup$ What have you tried? Could you state the subproblem here so that we all can discuss about it and why you guess the pricing problem changes? Are the known scheduled arrival times deterministic values? Is it a "simple" VRP or does it have time windows and/or limited capacities? Is there a maximum number of vehicles to use? $\endgroup$– dhassonCommented Aug 23, 2020 at 3:08
-
1$\begingroup$ May I ask way you insist that it should be solved using column generation? It seems funny to decide on a solution procedure before knowing how to solve the subproblem(s) $\endgroup$– SuneCommented Aug 23, 2020 at 9:09
-
$\begingroup$ @dhasson scheduled arrival time is deterministic. There are a max number of vehicles with limited capacity. $\endgroup$– BhrCommented Aug 23, 2020 at 9:51
-
$\begingroup$ @Sune my problem is in category of VRPs and based on litrature branch and price is one of good solution approached for this kind of problems. I 'm just trying to know may l solve my problem with this approach. This problem with cost objective function has been solved in lirature. so I think it is not funny!! $\endgroup$– BhrCommented Aug 23, 2020 at 9:54
-
$\begingroup$ It is allowed that the vehicle arrives later than the train at a node and just the arrival time in that node is calculated based on max time of the vehicle arrives in that node. Just I need to consider the sychronization in calculating the total time of each vehicle's tour. $\endgroup$– BhrCommented Aug 23, 2020 at 10:02
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
If I understood your problem correctly, then the only difference with the initial version (without the train) is that the time function is not additive.
For example, lets say the train passes through node $j$ at (given) time $t_j$, and you are computing a path $p$ whose last node is $i$. The total accumulated time on this path is denoted by $\tau_p(i)$. $\Delta t_{ij}$ denotes the time it takes for the vehicle to go from $i$ to $j$. If you want to extend the path and add node $j$, then the total accumulated time for path $p$, $\tau_p$, is increased as follows: $$ \tau_p(j) := \max\{ t_j, \tau_p(i) + \Delta t_{ij} \} $$
If the train arrives before the vehicle, then the total accumulated time takes value $\tau_p(i) + \Delta t_{ij}$, otherwise, it takes value $t_j$.
Note that this is like having time windows on your train nodes, with only a lower bound : you can just add time windows $[t_j, +\infty[$ on node $j$ and run your shortest path algorithm with time windows (if you have one at hand).
In other words the (time) resource extension function is not additive. This is handled for example by cspy, a great python library which computes shortest paths with resource constraints, where you can enter your own customized resource extension rule (check out the docs where such an example is given). VRPy, a VRP python library for the VRP relies on cspy to compute its shortest paths for column generation. Since VRPy handles time windows, you have got yourself a good starting point!
