As far as I know, the set of potential locations for facilities/depots and the set of demand points have no intersection in typical routing problems. In other words, those locations that are selected to be a depot have no demands to be satisfied. Is that true? If that is true, then why the literature considers this assumption?

I am asking this because when you consider classical facility location problems, it is the case that facilities are located exactly on demand points (in the model). Under the same assumption for a routing problem, no vehicle is used to collect demand of that node and deliver it to its depot. What do you think? Could you give some references in the literature where that is the case?


By routing problems I mean VRP and its variants (e.g., location routing etc) and not arc routing. By classical facility location models I mean discrete location models, where demands and candidate locations are discretized and integer programming techniques often used. According to the book "service science" (by Mark Daskin),

What this means in practice is that the service region will be divided into many small sub-areas. We will associate a demand with each sub-area and we will typically assume that the demand of that sub-area originates at a single point within the sub-area. The process of aggregating demand within a zone to a single point in the zone introduces a number of different errors (Hillsman and Rhoda, 1978; Erkut and Bozkaya, 1999; and Francis, Lowe, and Tamir, 2002). In most practical contexts, these errors are likely to be relatively small, however, compared at least to the more heroic assumptions made by either analytic models or continuous location models. In addition to discretizing the demands, there will be a discrete set of candidate sites.

asked 12 Oct '17, 04:16

Opt1989's gravatar image

accept rate: 0%

edited 12 Oct '17, 19:49

I'm not sure I know what a "typical" routing problem is. As Sune said in his answer, there is no general assumption that facilities are located at demand points or vice versa. In most of the routing problems I've seen, facilities and demand points are disjoint.

However, you have to take the scale or level of aggregation into account. Consider, for example, a package delivery service (FedEx, UPS, ...). They operate a set of facilities for long-haul trucks, then break up loads and do "last mile" delivery from a depot (possibly by handing off to USPS). It's entirely plausible (likely?) that designing and routing the long-haul portion is separate from the last mile portion. So they might well say, for example, that all demand in or near city X is to be handled by one depot near X, and (for purposes of the long-haul model) treat X as both a facility and a single demand point.

Similarly, if you are doing some planning model that involves a wide geographic scale (possibly air shipments between continents), you are not going to worry about the difference between two destinations a few miles apart. So you are likely to aggregate demand into a reasonably small number of regional loci, and then maybe limit depot locations to a subset of those loci.


answered 13 Oct '17, 11:38

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
accept rate: 19%

Thanks Paul. "typical" is not a technical terminology. By typical I mean those problems that I commonly see in relevant papers and books.

(13 Oct '17, 21:08) Opt1989

Usually it is not an assumtion that one can only locate at demand points, when you consider discrete location problems. Many of the instances considered in the literature have been generated by generating a set of potential facility sites and a set of demand points at random (in the plane or something like that). That is, the potential facility sites are not necessarily the same. On the other hand, if you are looking at location problems on graphs (p-median, p-center and problems lige them) the you are often limited to locations at the demand points (vertices of the graph).


answered 12 Oct '17, 15:05

Sune's gravatar image

accept rate: 20%

Thanks Sune. In all classical facility location problems I've seen the mathematical models do not distinguish between facilities and demand points, that is, they belong to the same set. However, they do not assume that demand of each node must be a positive number either. Even if we generate those sets independently, there is still a chance that a demand point becomes a facility. In that case, we should decide whether the same node satisfies its demand or others (as far as I know, in classical location models the same node does).

(13 Oct '17, 21:01) Opt1989

That is just the beauty of a discrete location problem: it does not matter, if a demand node is also a potential facility site. In that case, the point is just present in the set of demand points and the set of facilitet. In fact, we do not need the "points" (facilities or customers) to have any "geographical" meaning. They just represent a customer or a potential facility site. To name a few well cited papers where there is a clear distinction between facilities and customers, take a look at following:

(14 Oct '17, 05:41) Sune

"A comparison of heuristics and relaxations for the capacitated plant location problem", "Benders decomposition without separability: A computational study for capacitated facility location problems", and "Facility location models for distribution system design"

(14 Oct '17, 05:41) Sune

Thanks a lot:)

(14 Oct '17, 08:19) Opt1989
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]( "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: 12 Oct '17, 04:16

Seen: 1,888 times

Last updated: 14 Oct '17, 08:19

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