FREE ELECTRONIC LIBRARY - Abstract, dissertation, book

Pages:     | 1 |   ...   | 12 | 13 || 15 | 16 |   ...   | 20 |

«Automated Tourist Decision Support Wouter Souffriau Dissertation presented in partial fulfillment of the requirements for the degree of Doctor in ...»

-- [ Page 14 ] --

The GRILS heuristic is extended in order to deal with the distance constraint in a similar way like the other constraints. One distance constraint is defined per path. First, the importance of a distance constraint is defined as the sum of scores related to uninstantiated visit variables multiplied by their corresponding distance consumption (cheapest insertion) divided by the remaining distance budget. Next, the denominator of equation (5.11) is extended with the product of the importance of the distance constraint and the distance consumption.

The datasets of Gueguen [1999] are used, which extend data sets defined for the VRPTW [Solomon, 1987], for instances with 50 and 100 locations; distance constraints (L) of 50, 100 and 150; and m up to 10. Table 5.3 compares the performance of GRILS to that of the ILS approach of Garcia et al. [2010]. The first column indicates n, the number of locations, the second column distance constraint L. The second column gives the name of the test set over which the results are aggregated. The third column presents the results of Garcia et al. [2010], while the next three columns present the best, average and worst result of the GRILS approach, out of 10 runs. All solution qualities are presented as the procentual gap with the optimal results of Boussier et al. [2007] and are the average of m = 1 to m = 10. GRILS outperforms ILS, even with the worst results of 10 runs. Only the test instances with n = 50 and L = 50 seem to perform worse. The last two columns present the execution times of Garcia et al. [2010] and those of the GRILS approach, which are the sum of 10 independent runs. It can be concluded that the worst result of GRILS outperforms ILS using less computational effort, except for n = L = 50.

Note that Garcia et al. [2010] truncated the Euclidean distance between two locations to one decimal, which is standard for Solomon based test instances. If GRILS is run with the same precision, some test instances lead to better results than the optimal one of Boussier et al. [2007], who do not appear to apply any


–  –  –

rounding. When GRILS is run with a precision of rounding to 3 decimals (similar to no rounding but necessary to prevent floating point arithmetic errors), no better solutions are found than the “optimal” ones of Boussier et al. [2007]. This rounding is stricter than truncating to 1 decimal, as distances are always at least as long.

Finally, the results show that with the test instances of Boussier et al. [2007], the capacity constraint is never binding. If this constraint is removed, the same results can be obtained for all test problems. Thus, although the results for these SVRPTW instances are promising, another set of test problems is required to test the behaviour of the heuristic with multiple constraints.


Garcia et al. [2010] designed MCTOPTW test problems, based on the available test sets for the TOPTW. These test sets use one and two extra constraints, for m = 1 and m = 2. Table 5.4 compares the GRILS approach to the ILS approach of Garcia et al. [2010]. The first two columns state the number of paths m and the number of extra constraints Z. The third column states the test set on which the results presented were averaged. The next four columns respectively present the results of ILS and the best, average and worst results of 10 GRILS runs as the gap with the best solution known, as described in [Garcia et al., 2010]. The last two columns present the execution times of both approaches. On average, the best GRILS run outperforms ILS, however, using more computational effort. On the Cordeau–based instances, GRILS achieves a better results within the same computational time.

As the test sets of Garcia et al. [2010] are limited to two routes and two extra constraints, new test sets are defined to evaluate the proposed approach, reffered


–  –  –

to as “MCTOPTW Set 2”. Solomon’s *100 and Cordeau’s pr01 to pr09 instances, except pr06 for which no optimal solution is known, are extended with 11 extra constraints: one money budget constraint and 10 max–n type constraints. m ranges from 1 to 4. For the money constraint, each location is given a random entrance fee between 0 and 99. For each max–n type constraint, each location i has a 0.2 probability of ezi = 1, 0 otherwise. Ez is determined for each constraint, starting from a known (T)OPTW solution: for m = 1 the optimal solution of Righini and Salani [2006] is used, for m 1 the solution of Vansteenwegen et al. [2009]. Ez is the sum of all ezi, with i belonging to this solution. Designing the new test sets in this manner, this particular high quality (T)OPTW solution is also a feasible high quality solution of the new MC(T)OPTW problem. Therefore, a very good solution is known and can be compared with.

Table 5.5 presents the results of the GRILS approach on these new test problems.

The first column gives the number of paths m, the second column the origin of the test problems. The next three columns present the average gap (with the best known solutions on which the Ez were based) for the best, average and worst results of 10 independent runs. The last columns presents the execution times.

The results are very good: an average run has a score gap of only 3.26%, using 1 second of computational effort. In 27% of the test instances, the initial high quality solution was found, in 9% of the instances, this solution was improved. When m=1, even 70% of the optimal solutions were found.

Tests using a naive feasibility check, as mentioned in 5.3, lead to execution times that are 10 to 20 times higher for MCTOPTW Set 2, which indicates the necessity


–  –  –

for the intelligent neighbourhood consistency algorithm.

5.5.4 Parameter Sensitivity In this section, the influence of the different GRILS parameters is examined.

StartGreed, greedRange, greedDecrease and nrIterations are individually varied over a series of setting. The standard values are 0.89, 0.30, 0.01 and 100, respectively.

Also, a pure GRASP and a pure ILS version of the approach is examined and compared to the hybrid approach. The presented results are obtained using MCTOPTW Set 2.

Table 5.6 to 5.

9 present the influences of the different GRILS parameters individually.

The first column presents the parameter value. The next three columns present respectively the best, average and worst score gaps, averaged over MCTOPTW Set

2. The last column states the execution time as the sum of 10 runs, also averaged over MCTOPTW Set 2.

Table 5.6 presents the influence of the startGreed parameter.

Solution quality worsens as this parameter decreases in value. The table indicates that 0.99 is a better choice than the initial 0.89. This parameter has little or no influence on the execution time of the algorithm.

Table 5.7 presents the influence of the greedRange parameter.

Solution quality and execution time increase with this parameter. The table indicates that the 0.2 setting leads to higher quality best solutions in a smaller amount of time compared to 0.3. The average and minimal values, however, are slightly worse. Increasing


–  –  –

Table 5.8 presents the influence of the greedDecrease parameter.

Solution quality worsens as this parameter increases. A significant amount of computation time can be saved when a small amount of solution quality is sacrificed.

Table 5.9 presents the influence of parameter nrIterations.

It can be seen that an increase of this parameter leads to small improvements of the solution quality, and a significant increase in computational effort. In light of the envisioned tourist application, setting this parameter to 100 is a good compromise between quality and calculation time.

Table 5.10 compares the results of GRILS, with the standard parameter setting, to a pure GRASP approach (nrIterations set to 1), and to a pure ILS approach CONCLUSIONS 93

–  –  –

(startGreed = 1, greedRange = 0.01). Pure ILS outperforms pure GRASP, as it achieves better results in a smaller amount of computation time. GRILS achieves better results than the others, however, using significant computational effort.

–  –  –

5.6 Conclusions This chapter presents the Multi–Constraint TOPTW. This formulation enables to model entrance fees, max–n type constraints and mandatory POI-types.

A hybrid solution mechanism efficiently tackles MCTOPTW instances. The


proposed algorithm quickly propagates variable assignments in order to maintain a neighbourhood of possible insertions, which is explored heuristically using the importance of the different constraints as a common denominator. Moreover, this solution method also performs well on the TOPTW and the SVRPTW.

Solomon [1987]–based test instances are solved significantly better than Cordeau et al. [1997]–based instances, which have broader TWs. A “smart” 2-OPT procedure might reduce this gap by detecting a sequence of visits, with a broad common TW, and performing 2-OPT in order to reduce the total travelling time.

Another way to improve the results is to first look at the distribution of the TWs and identify “busy” periods, during which lots of visits are possible. For each of these busy periods, an extra constraint could be added. Their high importance will bias the insertions in less busy periods. Also, an integration of bottleneck scheduling approaches [Goldratt, 1984] seems appropriate.

Chapter 6

The City Trip Planner

This chapter presents the City Trip Planner, which is a web–based tourist decision support system that proposes city trips tailored to the user’s context and personal interests. The system plans city visits of multiple days, with for each POI multiple time windows which can differ from day–to–day. Moreover, lunch breaks can also be scheduled and the city’s tourist office can suggest a few POIs to be included in a trip. The City Trip Planner integrates the selection of POIs and the routing between them. To the best of the author’s knowledge, such an integrated system is unique.

In order to take opening hours into account, the MCTOPTW is extended with Multiple Time Windows (MCTOPMTW). Each vertex is extended allowing W TWs for each day, instead of one. Also, the TWs can be different on different days. An instance of the problem and a solution are presented by Figure 6.1. The multiple TW model overcomes the drawbacks of the (T)OPTW: opening hours of POIs can now be modelled by allowing multiple opening hours per day, and different opening hours each day.

The OP with Multiple TWs has recently been given attention by Tricoire et al.

[2010], who solve the Multi-Period OP with Multiple TWs, a generalisation of the TOPTW. In this problem, every vertex can also have more than one time window on a given day and time windows can be different on different days. They propose a Variable Neighbourhood Search (VNS) algorithm and embed an exact algorithm to deal with a path feasibility sub problem. Extensive experimental results show that they obtain high quality solutions for problems with 100 vertices and 2 paths in around one minute of computation time. The application described by Tricoire et al. [2010] is about facilitating the planning of future working days by field workers and sales representatives.

–  –  –

Figure 6.1: The Orienteering Problem with Multiple Time Windows This chapter is organised as follows.

Section 6.1 extends the OP mathematical definition and explains how extra tourist decision support functionalities can be modelled. In Section 6.2, the different components of the City Trip Planner are presented. Section 6.3 illustrates the usage of the City Trip Planner. Statistics and feedback are used to evaluate the system in Section 6.4. Finally, Section 6.5 concludes this chapter.

6.1 Mathematical Formulation

Based on the notation introduced in sections 2.1, 3.1, 4.1 and 5.1, the MCTOPMTW can be formulated as an integer program ( xijd = 1 if, in path d, a visit to vertex i is followed by a visit to vertex j, 0 otherwise; yiwd = 1 if vertex i is visited during TW w in path d, 0 otherwise; sid is the start of the service at vertex i in path d;

Oiwd and Ciwd are the opening and closing times of TW w of vertex i in path d;

M a large constant;):

–  –  –

The objective function (6.1) maximises the total collected score. Constraint (6.2) guarantees that all paths start in vertex 1 and end in vertex n. Constraints (6.3) and (6.4) determine the connectivity and time line of each tour. Constraints (6.5) guarantee that every vertex is visited at most once. Knapsack constraints (6.6) limit the selection by constraining attributes of the vertices. Constraints (6.7) restrict the start of the visit to the time window.

The multiple knapsack constraints (6.6) model of the previous chapter (constraints (5.6)) allowed to express the constraints that each location can be visited at most once, in addition to other more obvious usages. Section 5.2 explained how mandatory POI type constraints can be modelled by simply splitting up certain POIs and adding extra constraints. This same technique will now allow to model multiple TWs: locations with multiple TWs are split up into different visits to the same location, with one TW, and adding an extra constraint allowing only one visit to the actual location. Moreover, weather dependency can also be modelled by splitting up a POI: the POI with a TW marking a sunny period has a higher score than the same POI with a TW for a rainy period, and both can be visited at most once. In this case, Si should be replaced by Siwd in Equation 6.1.


6.2 System Architecture

Pages:     | 1 |   ...   | 12 | 13 || 15 | 16 |   ...   | 20 |

Similar works:

«УДК 378.146 ПОРТФОЛИО КАК СРЕДСТВО ИЗМЕРЕНИЯ ОБРАЗОВАТЕЛЬНЫХ РЕЗУЛЬТАТОВ Айснер Л.Ю., Бершадская С.В., Богдан О.В. Красноярский государственный аграрный университет, Красноярск, Россия Аннотация: Статья посвящена внедрению в современное высшее образование таких...»

«JJA Jordan Journal of the Arts, Vol.4 No.1, 2011, 65-98 The Influence of Arab and Related Cultures on the Style and Techniques of the Jordanian Folk Jewelry Khalil Tabaza, Faculty of Fine Arts, Yarmouk University, Irbid, Jordan. Received on April 1, 2009 Accepted on Feb. 21, 2010 ‫تأثير الحضارة العربية والعالمية على فن الصياغة الشعبية‬ ‫األردنية من حيث التصميم والتقنيات‬.‫خليل طبازة، كلية...»

«Process for IPv6 Migration in Large Organizations Pedro Filipe Martins de Castro Dissertation submitted to obtain the Master Degree in Communication Networks Engineering Examination Committee Chairperson: Prof. Paulo Jorge Pires Ferreira Supervisor: Prof. Ricardo Jorge Feliciano Lopes Pereira Member of the Committee: Prof. Artur Miguel do Amaral Arsénio October 2013 Abstract The shortage of IP addresses has become the bottleneck for Internet development. IPv4 has no longer the capacity to...»

«Nova Acta Leopoldina NF 111, Nr. 379, 205– 216 (2010) Implantation and Explantation of Active Subretinal Visual Prostheses Using a Combined Transcutaneous and Transchoroidal Approach Florian Gekeler1, Peter Szurman1, Dorothea BeSch1, Martin rohrBach1, Eberhart zrenner1, Karl Ulrich Bartz-Schmidt1, and Helmut SachS2 With 5 Figures Abstract We are reporting on the surgical technique for implantation and explantation of subretinal visual implants with extra-ocular and extra-corporeal parts. We...»

«EWGAE 2010 Vienna, 8th to 10th September Reinforcement effect on the ultrasonic pulse velocity in concrete, depending on the sounding method and measuring device U. LENCIS 1, A. ŪDRIS 2, A. KORJAKINS 3 Riga Technical University, Institute of Materials and Structures, Azenes 16/20, LV-1658, Riga, Latvia; uldis.lencis@inbox.lv, tel. and fax +371 67089138, 2 aigars.udris@rtu.lv, tel. +37167089240, aleks@latnet.lv, tel. +37167089248 Keywords: Concrete, nondestructive testing, ultrasonic pulse...»

«    Conference Proceedings Graz, March 30th and 31st, 2016 organized by the Institute of Paper, Pulp and Fibre Technology Institute of Process and Particle Engineering Programand Organizing Committee: Wolfgang Bauer Wolfgang Fischer Thomas Gamse Ulrich Hirn Peter Loidolt Jakob Redlinger-Pohn Stefan Radl Adela Roller Kerstin Schefzik Titlepage Source of Figures: Campus „Alte Technik“: © Graz University of Technology Simulated Particles: Loidolt, P., 12th Minisymposium VT, Graz, 2016...»

«Curriculum Vita 1. Personal Data a. Name and Title Dong Qian, Associate Professor of Mechanical Engineering Department of Mechanical Engineering 800 West Campbell Road, EC38 University of Texas at Dallas, Dallas, TX 75080-3021 Assistant Editor, Journal of Computational Mechanics (2012) Tel.: (972) 883-4890; Fax: (972) 883-4659 E-mail: dongqian.work@gmail.com (preferred) or dong.qian@utdallas.edu Web-page: me.utdallas.edu c. Education Ph.D. Mechanical Engineering, 2002 Northwestern University,...»

«TECHNISCHE UNIVERSITÄT MÜNCHEN Fakultät Wissenschaftszentrum Weihenstephan für Ernährung, Landnutzung und Umwelt Lehrstuhl für Experimentelle Genetik Physiology and molecular characterization of metabolism related mouse models for bone disease Shen Chi Vollständiger Abdruck der von der Fakultät Wissenschaftszentrum Weihenstephan für Ernährung, Landnutzung und Umwelt der Technischen Universität München zur Erlangung des akademischen Grades eines Doktors der Naturwissenschaften...»

«Technische Fakultät Albert-Ludwigs-Universität, Freiburg Lehrstuhl für Kommunikationsysteme Prof. Dr. Gerhard Schneider Master thesis Abstract Unattended Workflow Interactions January 18, 2012 Supervisors Dirk von Suchodoletz Klaus Rechert First Reviewer Prof. Dr. Gerhard Schneider Alibek Kulzhabayev Second Reviewer Matr.-Nr.: 2950774 Prof. Dr. Christian Schindelhauer Erklärung Hiermit erkläre ich, dass ich diese Abschlussarbeit selbständig verfasst habe, keine anderen als die...»

«DIAMOND FILMS AND COATINGS Development, Properties, and Applications Edited by Robert F. Davis North Carolina State University Department of Materials Science and Engineering Raleigh, North Carolina NOYES PUBLICATIONS Park Ridge, New Jersey, U.S.A. Copyright © 1993 by Noyes Publications No part of this book may be reproduced or utilized in any form or by any means, electronic or mechanical, including photocopying, recording or by any information storage and retrieval system, without permission...»

«Nova Acta Leopoldina NF 111, Nr. 379, 127– 136 (2010) New Techniques to Measure Lens Tilt, Decentration and Longitudinal Chromatic Aberration in Phakic and Pseudophakic Eyes Frank SCHAEFFEL (Tübingen) and Hakan KAYMAK (Düsseldorf) With 7 Figures Abstract A new automated technique is presented to measure lens tilt and decentration in phakic and pseudophakic human eyes, along with new data on the variances of these variables in the phakic eye. Our data shows that the natural lens has variable...»

«Designing an Exploratory Text Analysis Tool for Humanities and Social Sciences Research Aditi Shrikumar Electrical Engineering and Computer Sciences University of California at Berkeley Technical Report No. UCB/EECS-2013-203 http://www.eecs.berkeley.edu/Pubs/TechRpts/2013/EECS-2013-203.html December 13, 2013 Copyright © 2013, by the author(s). All rights reserved. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided...»

<<  HOME   |    CONTACTS
2016 www.abstract.xlibx.info - Free e-library - Abstract, dissertation, book

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.