Vehicle routing (and related problems-
VRPs) was centrally the topic of my PhD at MIT. Even though this is not the research area in which I have the highest number of publications, it is surely the one for which I
have the highest number of citations. In Google Scholar, my top 5 publications, citations-wise, are in this area.
Most of my
publications in this area were written when I was at MIT, however there have also
been some publications afterwards, both when I was at NTUA and when I went to
DTU. Below is a rough description.
MIT
My PhD thesis at MIT, supervised by Amedeo Odoni (a professor at the Departments of Aeronautics and Astronautics and of Civil Engineering), was completed in
September of 1978. It examined two methodologically related problems: (a) the
optimal sequencing of aircraft landings, and (b) the single vehicle dial-a-ride
problem, both static and dynamic. In both problems, dynamic programming
algorithms were developed. The thesis won the 1978 PhD dissertation award of
the Transportation Science and Logistics (TSL) section of ORSA, the Operations
Research Society of America (a precursor of INFORMS)- that prize was awarded in 1979. Papers No.
1 and 2 below were published as a result of the PhD thesis.
According to the literature, Paper No. 1 is the first paper that talked (among other things) about dynamic VRPs. When you put Dynamic Vehicle Routing in Google Scholar, two of the top 3 results are my papers.
Research on dial-a-ride continued while I was a
faculty member at MIT, in the context of the following two projects, both
funded by two separate agencies of UMTA, the Urban Mass Transportation
Administration of the US Department of Transportation:
·
“Simple Performance Models for Flexible-Route Feeder
Transportation Systems” (September 1980- September 1983) University Research
Program, UMTA. Amedeo Odoni and I were Co-Principal Investigators.
· “Advanced Dial-A-Ride Algorithms Research Project” (December 1980-
September 1983) Panatransit Integration
Program, UMTA. Amedeo Odoni, Nigel Wilson and I were Co-PIs. Nigel was a professor at the Civil Engineering Department at MIT.
Papers No. 7 and 8 below were produced as
a result of this research, however in parallel I also wrote papers No. 3, 4, 5
and 6 which were also related.
Paper No.
6 is my favorite paper of all time (!), discussing asymptotic optimality in
heuristic VRP algorithms. It was not funded by any project.
Paper No. 7 was associated with the PhD
thesis of Jang Jei Jaw, supervised by Amedeo Odoni (I was on his PhD thesis
committee). That paper was ranked No. 40 (or top 1.5%) in Web of Science citations among
2,697 papers published in Transportation
Research Part B (Methodological) during the period 1979-2019.
Later at MIT I also did research on the
routing and scheduling of ships, and more precisely:
·
“Dynamic Cargo Ship Routing and Scheduling Problems: Analysis and
Solution Techniques” (July 1982- June 1983). MIT Center for Transportation
Studies (CTS). Jim Orlin (a colleague at the Sloan School of Management) and I were Co-PIs.
·
“Analysis and Solution Algorithms of Sealift Routing and
Scheduling Problems” (March 1983- May 1988). Office of Naval Research (ONR).
Jim Orlin and I were Co-PIs.
Both projects were with Jim Orlin, who started his academic career at MIT the same time as me (July
1979). I knew Jim from the MIT Operations Research Center, of which I was among the affiliated faculty. The first project was seed money from the MIT CTS. We used
that money to get the bigger project from ONR. The actual money came from the
US Military Sealift Command (MSC), who wanted us to develop algorithms to route
and schedule their cargo ships in the case of a mobilization situation.
Paper No. 9 was –at least indirectly- connected to this project, in fact it was an invited chapter on dynamic vehicle routing problems in a vehicle routing book by Bruce Golden and Arjang Assad.
Papers
No. 10 and 12 were also connected to this project, being associated to the PhD
theses of Tai Up Kim and Paul Thompson, respectively (I supervised both). Kim was an Ocean Engineering student, and Thompson was with the MIT OR Center. Co-authors
in paper No. 10 were (the late) Marius Solomon (Northeastern Univ.) and Tom
Magnanti (MIT Sloan), in addition to Tai Up Kim.
Paper No. 11 (with John Tsitsiklis, MIT EECS) was a paper on dynamic shortest paths when arc costs were Markovian, which was partially funded by the following Draper Lab project, which I got just before I left MIT in 1989 and which actually started when I left MIT!
- Advanced Algorithms for Automated Mission and Trajectory
Planning” (July 1989- June 1990).The Charles Stark Draper Laboratory.
See also the "other research" section and look for Project Athena at MIT.
NTUA
I had no vehicle routing projects at NTUA.
In fact my position there was on maritime transport economics and management and
had only a marginal connection with OR, let alone vehicle routing. However, I managed to write some VRP- related papers, some in my
spare time, for instance paper No.
13, a survey on dynamic VRPs.
But it was paper No. 14 that was odd (in a sense). Published in EJOR, some 16 years after I had last published a VRP
paper, it was a paper on pick up and delivery problems, whose dynamic programming algorithm I was proud to personally encode in Fortran 95! That was
actually the first code I wrote since my PhD thesis, some 33 years earlier.
That paper marked my first attempt to re-engage in OR. I decided to re-engage
after realizing that this was where most of my citations were, whereas most of
my publications in other areas produced far less citations. I wrote that paper in my spare time.
DTU
On paper at least, DTU was a better
environment for VRP (or OR) research than NTUA, and my position there was in
transport optimization. However, the only VRP- relevant project was Concoord (a
multi-partner project coordinated by Tom van Woensel of Univ. Eindhoven). Within that project I wrote a survey paper on dynamic VRPs (paper No. 15), with Min Wen and Christos Kontovas. That
paper is No. 2 (or top 0.18%) in downloads and No. 21 (or top 2%) in Web of
Science citations among nearly 1,100 papers published in Networks during
the period 1999-2020.
Paper No. 16 (a bit controversial as it criticizes papers that put methodology before the actual problem formulation) was
not funded by any project.
Papers No. 17 and 18 were on ship weather routing
and were funded by the SIMOS project at DTU:
- SIMOS, DTU partner in a project on ship weather routing, DTU Space Leader,
funded by Denmark’s Innovation Fund (2017-2020).
Prior to SIMOS, we also had another ship weather routing project:
- BLUESIROS, partner in a project on maritime weather routing, DTU Space
leader, funded by the European Space Agency (2016-2018).
I also organized and chaired the ROUTE 2014 and ROUTE 2018 workshops on behalf of DTU, and kept alive the
tradition started by Oli Madsen of DTU. It was great seeing many VRP experts once
again.
A partial set of VRP papers/articles/PPTs of mine can be found HERE.
Some papers in other areas (for instance ship
speed optimization combined with route optimization) can also be considered to
fall in the VRP area. See section on ship speed.
VRP-related papers:
1.
Psaraftis,H.N., 1980, A Dynamic Programming Solution to the
Single-Vehicle Many-to-Many Immediate-Request Dial-A-Ride Problem, Transportation
Science 14, No.2, 130-154.
2.
Psaraftis,H.N., 1980, A Dynamic Programming Approach for
Sequencing Groups of Identical Jobs, Operations Research 23,
No.6,1347-1359.
3.
Psaraftis,H.N., 1983, Analysis of an O(N²) Heuristic for the
Single-Vehicle Many-to-Many Euclidean Dial-A-Ride Problem, Transportation
Research 17B, No.2, 133-145, 1983.
4.
Psaraftis,H.N.,k-Interchange Procedures for Local Search in a
Precedence- Constrained Routing Problem, European Journal of Operational
Research 13, No.4, 391-402.
5.
Psaraftis,H.N., 1983, An Exact Algorithm for the Single-Vehicle
Many-to-Many Dial-A-Ride Problem with Time Windows, technical note, Transportation
Science 17, No.3, 351-357.
6.
Psaraftis,H.N., 1984, On the Practical Importance of Asymptotic
Optimality in Certain Heuristic Algorithms, Networks 14, No.4 587-596.
7.
Jaw, J-J,A.R.Odoni, H.N.Psaraftis, N.H.M.Wilson, 1986, A Heuristic
Algorithm for the Multi-Vehicle Advance-Request Dial-A-Ride Problem with Time
Windows, Transportation Research 20B, No.3, 243-257.
8.
Psaraftis,H.N., 1986, Scheduling Large-Scale Advance-Request
Dial-A-Ride Systems, American Journal of Mathematical and Management
Sciences 6, Nos.3-4, (special issue on vehicle routing with time windows)
327-367.
9.
Psaraftis,H.N., 1988, Dynamic Vehicle Routing Problems, in Vehicle
Routing: Methods and Studies, B.Golden and A.Assad (eds), North Holland.
10.
Psaraftis,H.N., M.M Solomon, T.L.Magnanti, T.U. Kim, 1990, Routing
and Scheduling on a Shoreline with Release Times, Management Science 36,
No.2 212-223.
11.
Psaraftis,H.N., J.N.Tsitsiklis, 1993, Dynamic Shortest Paths in
Acyclic Networks with Markovian Arc Costs, Operations Research 41, No. 1, 91-101 (special issue on Dynamic
and Stochastic Transportation Models).
12.
Thompson,P.M., H.N.Psaraftis, 1993, Cyclic Transfer Algorithms for
Multi-Vehicle Routing and Scheduling Problems, Operations Research 41,
No. 5, 935-946.
13.
Psaraftis, H.N., 1995, Dynamic Vehicle Routing: Status and
Prospects, Annals of Operations Research
61, 143-164.
- Psaraftis, H.N., 2011, A multi-commodity,
capacitated pickup and delivery problem: The single and two-vehicle cases,
European Journal of Operational Research 215, 572–580.
- Psaraftis, H.N., M. Wen and C.A. Kontovas, 2016, Dynamic Vehicle
Routing: Three Decades and Counting, Networks Vol. 67, issue 1, 3-31, DOI 10.1002/net. 21628.
- Psaraftis, H. N., 2017, Ship
routing and scheduling: the cart before the horse conjecture, Maritime
Economics and Logistics, Vol. 17, Issue 2, 1-14.
- Zis, T., Psaraftis, H.N., Ding, L., 2020, Ship
weather routing: a taxonomy and survey, Ocean Engineering, vol.
213, DOI: 10.1016/j.oceaneng.2020.107697.
- Zis, T. and Psaraftis, H.N., 2020,
Weather Routing in Maritime Shipping: a Review and Future Outlook. Transportation Research Board 98th Annual Meeting, Washington D.C.,
USA, January 2020.
