Hi Mukul,
I have CC'd the dev list because these are good questions and others might have opinions also.
"user" is not defined so the problem is hard to answer. We have lots of users that have different requirements. For example:
A user of a web application? or a user of SQL?
We need to separate the data model from the presentation model. The presentation layer talks to someone like a web user. The SQL user expects data in table like structures and can easily be queried.
pgRouting in general is an engine that deals with solving problems that are primarily represented as tables of data.
So for most VRP like solvers we will have tables of data that get passed to the solver and the solver will return a set of records that look like a table.
So I could see a table of:
vehicles - to describe the vehicles capacity, efficiency, etc
orders - a list of orders to pickup or deliver, and their locations,
and time windows if needed
depot - list of depots if not encoded in the order table.
Often we can represent depots in the order table with special ids or a flag.
Vehicles are assumed to be parked at the depot. But they could also have a "home" location associated with them that they leave and return to.
The results would be a set of records like:
seq, vehicle, depot, -1, depart - leave the depot
seq, vehicle, order, arrive, depart - pickup/deliver and order
...
seq, vehicle, depot, arrive, -1 - returns to the depot
<repeat for each vehicle>
Does this make sense?
Ask Daniel to forward to you the SmartVRP demo he built based on last years code.
-Steve
On 3/13/2014 3:06 PM, Mukul priya wrote:
Hi ,
I have been reading a lot about TSP(asymmetric)and VRP (its different
versions) . I think the best implementable approach for both of them is
to follow the local search or tabu search.I have a few points that we
need to discuss.1). it is important to implement vrp(any version) in such a way that a
user finds it easy to utse it and interpret the results. I would like
to discuss more about the structure that we can use to store the depot
information , vehicle information and cosutomer information .2).Now if we think from users perspective these must be the input that
our procedure will need so some discussion on how we are going to fetch
these inputs form the user needs to be done .3) As both of you mentioned we need to set some achievable goals and
then extend on that . So we will try to first achieve the basic solution
to VRP and then suppose we get lucky and have an optimized solution ,we
can then extend our goals .The other thing i wanted to ask was regarding two proposals on the
same topic (VRP) (even though the proposals will be on different
versions of it ) and questions might be raised by the osgeo committee
regarding it . So i wanted your suggestion whether i should make a
proposal on some different topic like Assymetric TSP ( It is almost the
same thing as VRP and It can also be solved using local search or 3-opt
or tabu search).The category of the problems is same so i won't have any
issue with that.-
MukulOn Thu, Mar 13, 2014 at 6:42 AM, Stephen Woodbridge
<woodbri@swoodbridge.com <mailto:woodbri@swoodbridge.com>> wrote:On 3/12/2014 9:04 PM, Daniel Kastl wrote:
On Thu, Mar 13, 2014 at 7:44 AM, Manikanta Kondeti
<mani.iiit123@gmail.com <mailto:mani.iiit123@gmail.com>
<mailto:mani.iiit123@gmail.com
<mailto:mani.iiit123@gmail.com>__>> wrote:Hi sir ,
Thank you for fast and positive(
) response.
I have Mid-term exams till 15th starting from today. I am
almost
done with my proposal except the implementation part and
also met
mukul regarding the idea and proposal. I'm working on
VRP-PDPTW. He
is also working on other variation of VRP i.e... CVRP. I
hope that
won't be a problem ? . Will share the proposal with both
you in less
than 2 days.OK. That's good to hear.
Just try to make your proposals distinguishable enough, so we don't
later get asked why pgRouting needs another VRP algorithm.Also, like the Coursera seminar mentions, too, try to start with
something more simple and improve the algorithm then step by step.
With GSoC you always need to make sure, that there is a goal you can
achieve even if something goes unexpectedly.
So it's better to set some milestones, even some optional ones, like
adding support for multiple depot or multiple capacities when
there is time.Yes, this is VERY important. Students tend to be very optimistic and
set grandiose goals. I like to see these are our minimum goals and
these are our optional stretch goals if we have extra time.Coding the TABU search outside of of pgrouting is usually pretty
easy, stuffing it into postgresql and debugging there always is
harder than you think. Talk to Mukul about his experiences.We will help you set reasonable milestones for your projects if we
have a chance to review them before the deadlines.Thanks,
-SteveRegards,
DanielThanks ,
ManikantaOn Thu, Mar 13, 2014 at 1:56 AM, Daniel Kastl
<daniel.kastl@georepublic.de
<mailto:daniel.kastl@georepublic.de>
<mailto:daniel.kastl@__georepublic.de
<mailto:daniel.kastl@georepublic.de>>>
wrote:On Thu, Mar 13, 2014 at 5:18 AM, Stephen Woodbridge
<woodbri@swoodbridge.com
<mailto:woodbri@swoodbridge.com>
<mailto:woodbri@swoodbridge.__com
<mailto:woodbri@swoodbridge.com>>> wrote:Hi Manikanta,
Daniel is fine with you going forward with the PDPTW
proposal. He was just asking how it is different
from the
DARP code we already have because he is not
familiar with
the details of the various problems and solution.Anyway, You are fine proceeding with your plan.
Thanks,
-SteveHi Manikanta,
Steve is right.
I just asked about the differences, because I had no
time to
read the paper in details
It's probably a good idea, if you make sure that you
and Mukul
don't submit something that is too similar.Daniel
--
Georepublic UG (haftungsbeschränkt)
Salzmannstraße 44,
81739 München, GermanyeMail: daniel.kastl@georepublic.de
<mailto:daniel.kastl@georepublic.de>
<mailto:daniel.kastl@__georepublic.de
<mailto:daniel.kastl@georepublic.de>>
Web: http://georepublic.infoTel: +49 (089) 4161 7698-1
<tel:%2B49%20%28089%29%204161%__207698-1>
Fax: +49 (089) 4161 7698-9
<tel:%2B49%20%28089%29%204161%__207698-9>Commercial register: Amtsgericht München, HRB 181428
CEO: Daniel Kastl--
Georepublic UG (haftungsbeschränkt)
Salzmannstraße 44,
81739 München, GermanyeMail: daniel.kastl@georepublic.de
<mailto:daniel.kastl@georepublic.de>
<mailto:daniel.kastl@__georepublic.de
<mailto:daniel.kastl@georepublic.de>>
Web: http://georepublic.infoTel: +49 (089) 4161 7698-1
Fax: +49 (089) 4161 7698-9Commercial register: Amtsgericht München, HRB 181428
CEO: Daniel Kastl
