jomavera / branchandpricevrp

Test on how to implement Branch and Price for VRP with Gurobi (work in progress)

Branch and Price for Vehicle Routing Problem

Description

This repository contains an (incomplete) implementation of Branch and Price for the Vehicle Routing Problem. The branching is generated as describe in section 4.5.2 of On-Time Last-Mile Delivery: Order Assignment with Travel-Time Predictors. Node exploration is according a priority queue.

Prerequisites

• Python 3.8
• gurobipy 9.1.0
• sklearn 0.24.2
• numpy 1.20.2

branchandpricevrp's Issues

Cycling

The node exploration enters to a cycle

Is tree structure and pruning necessary?

Hi, jomavera

Thank you very much for the code, but I have some questions. In some textbooks on branch pricing algorithms, it seems that the nodes are stored in a tree structure and pruned using upper and lower bounds. In your algorithm, priority queue is used and there seems to be no upper bound and pruning logic, are both correct?

Looking forward to your recovery, thank you very much!

About Code integrity

Excuse me, I'm working on the branch-and-price algorithm in VRP and I found your code very instructive. But it is said that in README this code is incomplete. So I would like to know whether the code had been corrected before and had been completed. Thank you!! This makes a lot of sense to me.

branching procedure

Excuse me, I've been working on branching and price algorithms lately and your code has inspired me, have you continued to work on the branching procedure?