I’m developing a linear program of VRP with additional features for a solver. I’m looking for a corresponding mathematical formulation of my model.

The problem is a CVRP with additional features. There are 1 depot and numerous customer nodes. Each customer node has pick-up and delivery demand. At first, all the pick-ups are collected and delivered to the depot. Then, all vehicles wait in the depo while sorting is done (sorting operation is outside the model). Afterwards, cargo is delivered from depo to delivery nodes.

I found a formulation of 2-echelon problem, but it doesn’t fit because I have single fleet of vehicles. Ordinary Pick-up and delivery model also doesn’t fit.

asked 16 Aug '16, 05:52

Ivan%20Zykov's gravatar image

Ivan Zykov
accept rate: 0%

Your problem is not a VRP with pick-up and delivery as pick-ups and deliveries are done separately. In the literature, this problem is known as the vehicle routing problem with cross-docking (the intermediate facility is known as the cross-dock in the SCM and logistics). There are numerous mathematical models in the literature depicting different variations of this type of operation. I'm not sure which article considers your case as many studies considers time windows and different fleets for pick-ups and deliveries. However, I think the adaptation of a basic model to your case is not very hard (i.e., you have to ensure that a vehicle is not used for pick-ups and deliveries at the same time). The easy way is to enforce that the start of all deliveries happens after finishing all the pick-ups and sortings.


answered 16 Aug '16, 07:33

Ehsan's gravatar image

Ehsan ♦
accept rate: 16%

Thank you for the suggestion. I considered cross-docking before. As I understand, the model plans routing and sorting operations in the depo, i.e. how cargo should be interchanged between vehicles. In my case we don’t care about sorting operation, I need a simpler model.

So far, I developed a modification of CVRP that seems to work, but there might be a more efficient formulation.

(16 Aug '16, 08:53) Ivan Zykov

You're welcome. Unfortunately, I'm not aware of such formulation.

In case you don't care about the sorting operations, you could omit its corresponding constraints from the model and link the pick-up and delivery decisions directly. Also, if you don't have any time window constraint, then a CVRP formulation shoud be applicable to your case with some input data manipulation.

(16 Aug '16, 09:28) Ehsan ♦
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported



Asked: 16 Aug '16, 05:52

Seen: 1,010 times

Last updated: 16 Aug '16, 09:28

OR-Exchange! Your site for questions, answers, and announcements about operations research.