[pgrouting-dev] GSoC Proposal
Stephen Woodbridge
woodbri at swoodbridge.com
Thu Mar 13 12:42:21 PDT 2014
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.
>
>
> -
> Mukul
>
>
>
> On Thu, Mar 13, 2014 at 6:42 AM, Stephen Woodbridge
> <woodbri at swoodbridge.com <mailto:woodbri at 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 at gmail.com <mailto:mani.iiit123 at gmail.com>
> <mailto:mani.iiit123 at gmail.com
> <mailto:mani.iiit123 at 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,
> -Steve
>
> Regards,
> Daniel
>
>
> Thanks ,
> Manikanta
>
>
> On Thu, Mar 13, 2014 at 1:56 AM, Daniel Kastl
> <daniel.kastl at georepublic.de
> <mailto:daniel.kastl at georepublic.de>
> <mailto:daniel.kastl at __georepublic.de
> <mailto:daniel.kastl at georepublic.de>>>
> wrote:
>
>
>
>
> On Thu, Mar 13, 2014 at 5:18 AM, Stephen Woodbridge
> <woodbri at swoodbridge.com
> <mailto:woodbri at swoodbridge.com>
> <mailto:woodbri at swoodbridge.__com
> <mailto:woodbri at 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,
> -Steve
>
>
> Hi 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, Germany
>
> eMail: daniel.kastl at georepublic.de
> <mailto:daniel.kastl at georepublic.de>
> <mailto:daniel.kastl at __georepublic.de
> <mailto:daniel.kastl at georepublic.de>>
> Web: http://georepublic.info
>
> Tel: +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, Germany
>
> eMail: daniel.kastl at georepublic.de
> <mailto:daniel.kastl at georepublic.de>
> <mailto:daniel.kastl at __georepublic.de
> <mailto:daniel.kastl at georepublic.de>>
> Web: http://georepublic.info
>
> Tel: +49 (089) 4161 7698-1
> Fax: +49 (089) 4161 7698-9
>
> Commercial register: Amtsgericht München, HRB 181428
> CEO: Daniel Kastl
>
>
>
More information about the pgrouting-dev
mailing list