# Column Generation algorithm

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?

• 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? – dhasson Aug 23 '20 at 3:08
• 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) – Sune Aug 23 '20 at 9:09
• @dhasson scheduled arrival time is deterministic. There are a max number of vehicles with limited capacity. – Bhr Aug 23 '20 at 9:51
• @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!! – Bhr Aug 23 '20 at 9:54
• 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. – Bhr Aug 23 '20 at 10:02

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).