Hi. I'm trying to find a suitable analytics method to solve the following hypothetical problem.

I have 1000 salesmen that I want to send to 100 different destination addresses throughout a country. At the moment, they are sent fairly randomly - with some people needlessly travelling very large distances.

This I could solve fairly easily with a linear optimisation method - with distance between salesmen and destination addresses being the cost which I want to minimise, and the constraints being the number of salesman, and e.g. number of visits required (the Transportation Problem, I believe).

Here's the problem though. What if I wanted to add constraints/conditions which say for example: I want five highly paid salesman with experience in Virtual Reality to go this address, along with three low paid ones with experience in board games. To another address, I might want a dozen board game sellers, but half a dozen medium paid retro computer sellers. And to do all of this, which still minimising that journey length.

Is this possible with an Operations Research-type approach? Is it sensible to take this approach or are there cognitive computing/neural network methods which could get there more easily? Could it scale to 10,000 individuals?

Many thanks in advance!

asked 20 Jul '17, 11:26

Ginger1's gravatar image

Ginger1
132
accept rate: 0%


If your sales staff visit one customer and return to base, then you are correct about the simple version, and the more complicated version sounds like a multi-commodity transportation problem (where the "commodities" are specific flavors of sales people, e.g. "highly paid with VR experience"). Barring additional unstated complications, you should be able to model it as a transportation problem by creating supply nodes for each combination of salesperson category and base location (or, if all come from the same base, just category) and demand nodes for each combination of customer location and category of salesperson. So, for instance, you might have one demand node for customer X with a demand of five highly compensated VR experts, and another demand node for customer X for three low-paid board games sellers.

link

answered 20 Jul '17, 11:45

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412
accept rate: 19%

Many thanks Paul for your reply. Knowing it is possible is a relief. Having researched, following your answer, multiple-commodity problems (leading me to discover multi-commodity network flow and numerous papers on workforce scheduling) it seems this is a common problem.

I think your suggested approach is to expand the number of supply/demand nodes to capture the various permutations of supply/demand available/required (respectively). This makes sense.

My only concern is the size of the potential problem space (in reality, I have probably around 70 types of "salesman", at potentially thousands of start locations - although this latter number could be reduced by putting people into geographical boxes). Still, I shall attempt to solve it with a simplified data set, and expand from there.

Many thanks again.

(24 Jul '17, 04:37) Ginger1

You're welcome. FWIW, the expanded transportation problem is a linear program, not an integer linear program. Modern LP solvers can handle zillions of variables pretty comfortably, and the constraint matrix of a transportation problem is fairly sparse (promoting faster solution).

If this works out for you, might I ask that you accept the answer (the check mark button)?

(24 Jul '17, 08:14) Paul Rubin ♦♦
1

Accepted. Working well in Python with PuLP, I'm pleased to report. Thank you again.

(03 Aug '17, 10:03) Ginger1
Your answer
toggle preview

Follow this question

By Email:

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

By RSS:

Answers

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

Tags:

×231
×2
×2

Asked: 20 Jul '17, 11:26

Seen: 341 times

Last updated: 03 Aug '17, 10:03

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